【黑客】树状数组进阶

黑客 · 2020-02-24 22:25:28 · 个人记录

树状数组的进阶操作详解

开头语

最近偶然看到树状数组，然后发现自己只记得单点修改区间查询和区间修改单点查询了。于是上网膜拜了几位大佬的博客，就把这个写下来，加深一下记忆。

首先，这个是树状数组：

区间修改单点查询

实现区间修改单点查询，就要用到差分。用这个树状数组维护 a[n] 的差分值。即 c[i]=a[i]-a[i-1]。修改时只需要修改 l 和 r+1 就好了。查询时从 1 加到 i 就是 a[i] 的值了。

区间修改区间查询

区间修改区间查询之前忘记了，网上的博客我感觉没写得太清楚（应该是我太弱了），我不知道为什么要用 c2[i] 存 c1[i] (i-1)。所以我就手推了一下，过程如下：

既然 c[i]=a[i]-a[i-1]，那么求区间和，就是求 sum=a[1]+a[2]+a[3]+...+a[k-1]+a[k]。

且 a[i]=c[1]+c[2]+c[3]+...+c[i-1]+c[i]。

那么 sum=(c[1])+(c[1]+c[2])+(c[1]+c[2]+c[3])+...+(c[1]+c[2]+c[3]+...+c[k-2]+c[k-1])+(c[1]+c[2]+c[3]+...+c[k-1]+c[k])。

把式子展开，得 sum=c[1]*(k)+c[2]*(k-1)+c[3]*(k-2)+...+c[k-1] *2+c[k]*1。

由于每次求和之前，我们无法知晓k，所以我们不能直接存 c[i] (k-i+1)。

但是我们可以发现，c[i]*(k-i+1)=c[i]*k-c[i]*(i-1)。

所以我们只需要存 c[i] 和在 c2 中存 c[i]*(i-1)，要用的时候求 c[i]*k-c[i]*(i-1) 就行了。

单点修改区间求最值

最近才发现树状数组居然还能干前缀最值，但是觉得挺简单，于是手推了一下，没推出来（打脸），于是上网看了大佬博客，恍然大悟，发现自己很弱智。

对于普通的树状数组，只能做前缀和，这里要求做前缀最小/大值。由于最小值与最大值都和求和一样，属于可合并运算。

可合并运算就是得到两个值，可将这两个值合并成一个值得运算。比如得知一个区间的左半边的和为 x，右半边的和为 y，那么整个区间的和为 x+y。同样的，最小值，最大值，gcd 等都属与可合并运算。

由于同属可合并运算，所以运算的本质是一样的。所以查询时只要把加改成 min 或 max。而修改时，我们可以看到，对于每一个 t[i]，它所管理的是一些 a 的最小/大值，那么修改 a[j] 时，如果 a[j] 属于 t[i] 的管辖内，由于 a[j] 有可能是新的最小/大值，所以 t[i]=min(t[i],a[j])/max(t[i],a[j])。

二维区间修改区间查询

没想到吧，树状数组居然还有二维的，而且还是区间修改区间查询，妥妥的顶配版。

洛谷里有一道模板题上帝造题的七分钟。

首先，我们要把树状数组拓展成二维的，树状数组拓展成二维是比较简单的，在数组上加一维，循环时加一维就可以了。

就是这样：

void update(int x,int y,int k){
    for(int i=x;i<=n;i+=lowbit(i)){
        for(int j=y;j<=m;j+=lowbit(j)){
            t[i][j]+=k;
        }
    }
}
int query(int x,int y){
    int ans=0;
    for(int i=x;i;i-=lowbit(i)){
        for(int j=y;j;j-=lowbit(j)){
            ans+=t[i][j];
        }
    }
    return ans;
}

但是输出时就麻烦一点，不是简单的 query(r)-query(l-1) 了。

当我们想要求以 (a,b) 为左上顶点，(c,d) 为右下顶点，也就是图中的黄色矩形的和时，它的区间和等于 (c,d) 前缀和，减去 (c,b) 前缀和，减去 (a,d) 前缀和，再加上重合的 (a,b) 前缀和。

那么现在二维解决了，轮到区间修改区间查询了。

我们可以借鉴一维的区间修改区间查询，建立查分数组。但是二维的差分数组怎么建呢？有人说得好，差分是前缀和的逆运算。那么二维前缀和怎么算呢？我们可以知道，二维前缀和 s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]。而在一维中差分数组 d[i]=a[i]-a[i-1]，前缀和 s[i]=s[i-1]+a[i]，那么一一对照，d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]。

与一维类似，求 (x,y) 前缀和，sum=a[1][1]+a[1][2]+...+a[1][y]+a[2][1]+a[2][2]+...+a[2][y]+......+a[x][1]+a[x][2]+...+a[x][y]

而 a[i][j]=d[1][1]+d[1][2]+...+d[1][j]+d[2][1]+d[2][2]+...+d[2][y]+......+d[i][1]+d[i][2]+...+d[i][j]

代入，sum=(d[1][1])+(d[1][1]+d[1][2])+...+(d[1][1]+d[1][2]+...+d[1][y])+......+(d[1][1]+d[1][2]+...+d[1][y]+d[2][1]+d[2][2]+...+d[2][y]+......+d[x][1]+d[x][2]+...+d[x][y])

整理一下，sum=d[1][1]*n*m+d[1][2]*n*(m-1)+...

总之，d[i][j] 要用到 (x-i+1)*(y-j+1) 次。

展开 (x-i+1)*(y-j+1)=x*y-x*j+x-y*i+i*j-i+y-j+1=x*y-x*(j-1)-y*(i-1)+(i-1)*(j-1)

那么我们就用四个树状数组，分别存 d[i][j],d[i][j]*(j-1),d[i][j]*(i-1),d[i][j]*(i-1)*(j-1)。

我们会存储，查询，还要会修改。

对于修改 (a,b)-->(c,d)，只要对 (a,b)+x,(c+1,b)-x，(a,d+1)-x，(c+1,d+1)+x。

结束语

好啦，对于树状数组的进阶操作到这应该很简单明了了。

再见！

黑客出品