嘘~ 正在从服务器偷取页面 . . .

时间戳优化树状数组的频繁清空

数据结构

发布日期: 2022-07-20

更新日期: 2022-07-22

文章字数: 462

时间戳优化树状数组的频繁清空

来自@zx2017老师的ppt Orz

适用场景：

给定 $T$ 组数据，每组数据有 $Q$ 个询问，询问给定 $n$ 个数的区间和

数据范围：$T\le 2\times 10^5,~\sum Q \le 2\times 10^5,~n\le 5\times 10^5$

注意，这里只限制了 $\sum Q$ ，并没有限制 $\sum n$

对于每组数据不能直接去清空数组，因为 $T \times n$ 肯定爆炸

考虑维护一个时间戳now，也就是现在是第几组数据

对于是这组数据的，也就是t[i]==now的情况，直接用

如果不是这组数据的，我们要先清零，再加。

注意到 tree[i]=0,tree[i]+=v 其实等价于 tree[i]=v

由于我们只有查询到一个树上结点，才会去判断它的时间戳

因此这类题目的时间复杂度可以控制在 $O(\sum Q \log \sum Q)$

修改部分的代码：

int tree[N],t[N],now=0;
void add(int x,int v)
{
    for(int i=x; i<=n; i+=lowbit(i))
        if(t[i]==now)tree[i]+=v;
        else t[i]=now,tree[i]=v; // tree[i] = 0 + v
}
int sum(int x)
{
    int res=0;
    for(int i=x; i; i-=lowbit(i))
        if(t[i]==now) res+=tree[i];
        else t[i]=now,tree[i]=0; // res+=0
   	return res;
}