关于区间查询有个疑问

P3372 【模板】线段树 1

Skadiiiii @ 2024-10-23 13:27:08

这是100pts的区间查询

long long query(int id,int x,int y)
{
    if(x<=tr[id].l&&tr[id].r<=y)
        return tr[id].s;
    pushdown(id);
    int mid=(tr[id].l+tr[id].r)>>1;
    long long ans=0;
    if(x<=mid)ans+=query(id<<1,x,y);
    if(mid<y)ans+=query(id<<1|1,x,y);
    return ans;
}

这是10pts的区间查询

long long query(int id,int x,int y)
{
    if(x<=tr[id].l&&tr[id].r<=y)
        return tr[id].s;
    pushdown(id);
    int mid=(tr[id].l+tr[id].r)>>1;
    long long ans=0;
    if(x<=mid)ans+=query(id<<1,x,mid);
    if(mid<y)ans+=query(id<<1|1,mid+1,y);
    return ans;
}

可本蒟蒻觉得这两种query不是等价的吗?
查询id的左孩子时(x,y)和(x,mid)有什么区别?id的左孩子最右边不也只到mid吗? 求解答


by formu1 @ 2024-10-23 13:32:03

问题是当你y小于mid的的时候会有问题


by formu1 @ 2024-10-23 13:37:06

就是x和y全部堆在左边而且不与mid有交集的情况


by formu1 @ 2024-10-23 13:37:44

右边同理


by CEFqwq @ 2024-10-23 13:43:28

@Skadiiiii 如果 [x,y] 包含在 [x,mid] 中时,会导致 (y,mid] 这一段被算进去。

Skadiiiii 好卷啊/bx


by Skadiiiii @ 2024-10-23 20:09:18

@formu1 恍然大悟,感谢dalao解答


by Skadiiiii @ 2024-10-23 20:10:46

@CEFqwq 感谢解答。哪里卷了,还不是考前抱佛脚


by CEFqwq @ 2024-10-23 21:05:08

@Skadiiiii 祝金勾/bx


by Skadiiiii @ 2024-10-23 21:37:03

@CEFqwq 蓝勾都悬(


by CEFqwq @ 2024-10-23 21:40:48

@Skadiiiii 会赢的


|