Magolor 首页文章幻灯片归档标签
树状数组黑科技讲义
|OI
字数总计: 5.5k|阅读时长: 21 分钟

震惊！ $99\%$ 的人都不知道，树状数组还有这些功能……

本文中，简单介绍了: 树状数组的基本使用方法，下标平移和反转技巧，清零技巧，维护前后缀最值，二维树状数组，树状数组与差分的结合(包括区间加单点查询以及区间加区间查询)，树状数组上二分，树状数组代替简单线段树。没有探讨并简单探讨了关于树状数组进一步代替线段树和树状数组可持久化的问题，给读者留下了思考空间。


前言

咳咳。想当年我还没有退役的时候，一直感觉线段树太复杂，为了一点小操作就不得不写线段树非常牛刀杀鸡大材小用；而树状数组功能又太少。

曾经看过zkw线段树，但是感觉他的处理范围是开区间的，不是很优美，操作也不是很直观(菜鸡个人感觉勿喷)。最后到退役也没学。

经典的方法就这三个，自己发明数据结构也不是很靠谱。我试过简化线段树但是失败了，那么剩下的就是加强树状数组。

然后在我临退役之前就汇总+研究了许多树状数组科技。现在在这里无偿分享一下。


1.树状数组入门

这显然不是这篇博客的重点，树状数组教程随便在哪个网站上也能找到。这里只贴下代码，最普通的加法树状数组。

1
2
3
int c[MAXN+5];
inline void Add(int i, int v){for(;i<=MAXN;c[i]+=v,i+=i&-i);}
inline int Sum(int i){int r=0;for(;i;r+=c[i],i-=i&-i);return r;}

是的，树状数组单点修改和前缀求和都可以一行写完，没有什么奇特之处。虽然大家都知道但是再强调一下，树状数组只能维护支持可减性的信息。

在此后我们会经常用到lowbit函数i&-i的衍生物: 为了方便，我们记i+(i&-i)为节点i的父亲，记节点i-(i&-i)为节点i的前驱。注意一下，正如其名，i-(i&-i)这坨东西并不是儿子，因为这个节点的父亲并不一定是节点i，例如 $7$ 的前驱是 $6$ ，而 $6$ 的父亲显然不是 $7$ 而是 $8$ 。定义祖先路径为一个节点不断进行迭代找父亲的i += i&-i操作得到的节点集合，同理定义前驱路径。实际上，与线段树不同之处就在此，在研究树状数组的过程中，一般情况下只有节点的前驱和前驱路径是值的考虑的，而节点的儿子和后代则没有太大的价值。


这里分享一些经典而简单的小Trick.


树状数组下标从0开始

手动改就好了，一进来函数先++i不就行了么。同理也可以实现任意下标变换。(UPD 2019.07.25: 补充一句，当然，这意味着也可以支持负下标)

1
2
3
int c[MAXN+5];
inline void Add(int i, int v){for(++i;i<=MAXN;c[i]+=v,i+=i&-i);}
inline int Sum(int i){int r=0;for(++i;i;r+=c[i],i-=i&-i);return r;}

反转树状数组

类似于修改下标，如果要反转树状数组查询后缀和直接一进来函数先i = MAXN-i+1即可。

1
2
3
int c[MAXN+5];
inline void Add(int i, int v){for(i=MAXN-i+1;i<=MAXN;c[i]+=v,i+=i&-i);}
inline int Sum(int i){int r=0;for(i=MAXN-i+1;i;r+=c[i],i-=i&-i);return r;}

还有一种巧妙的写法，就是把修改和查询反着写。即修改的时候-=而查询的时候+=。

1
2
3
int c[MAXN+5];
inline void Add(int i, int v){for(;i;c[i]+=v,i-=i&-i);}
inline int Sum(int i){int r=0;for(;i<=MAXN;r+=c[i],i+=i&-i);return r;}


树状数组清零

实际上任何一个数组都可以这样做，而树状数组本质也只是一个数组。用时间戳优化即可。

1
2
3
4
int c[MAXN+5], b[MAXN+5], T = 1;
#define Clear (++T)
inline void Add(int i, int v){for(;i<=MAXN;c[i]=b[i]<T?v:c[i]+v,b[i]=T,i+=i&-i);}
inline int Sum(int i){int r=0;for(;i;r+=b[i]<T?0:c[i],i-=i&-i);return r;}


UPD 2019.07.25: 树状数组求最大最小值

啊，忘记了几个小Trick。现在补上.

最大值和最小值是不满足可减性的，树状数组是维护不了的，除非——不需要减。当维护前后缀最小值的时候就可以用树状数组。以最大值为例:

1
2
3
int c[MAXN+5];
inline void Add(int i, int v){for(;i<=MAXN;c[i]=max(c[i],v),i+=i&-i);}
inline int Sum(int i){int r=0;for(;i;r=max(r,c[i]),i-=i&-i);return r;}


UPD 2019.07.25: 二维树状数组

二维树状数组当然是 $O(\log ^2 n)$ 的。不过这东西不常用，瓶颈在于空间复杂度，比不上主席树。

当然，如果用哈希表来做二维坐标到一维坐标的映射，似乎也可以得到一个优秀的数据结构。不过还是要提醒，unordered_map只是理论上$O(1)$而已，实践上常数还是蛮大的。

1
2
3
int c[MAXN+5][MAXN+5]; //unordered_map<pair<int,int>,int> c;
inline void Add(int i, int j, int v){int _=j;for(;i<=MAXN;i+=i&-i)for(j=_;j<=MAXN;j+=j&-j)c[i][j]+=v;}
inline int Sum(int i, int j){int r=0,_=j;for(;i;i-=i&-i)for(j=_;j;j-=j&-j)r+=c[i][j];return r;}

2.树状数组+差分

树状数组区间加单点查询

显然直接用差分就可以做到。

1
2
3
4
int c[MAXN+5];
inline void _Add(int i, int v){for(;i<=MAXN;c[i]+=v,i+=i&-i);}
#define Add(l,r,v) (_Add(l,v),_Add(r+1,-v))
inline int Sum(int i){int r=0;for(;i;r+=c[i],i-=i&-i);return r;}


树状数组区间加区间查询

这也是一个很经典的Trick，考虑如果只维护差分数组，那么查询区间和实际上是:

因此只需要两个树状数组，一个维护 $\sum_{i=l}^rb_i$ ，另一个维护 $\sum_{i=l}^r i \cdot b_i$ 即可。

1
2
3
4
5
int c[MAXN+5],s[MAXN+5];
inline void _Add(int i, int v){for(int j=i*v;i<=MAXN;c[i]+=v,s[i]+=j,i+=i&-i);}
#define Add(l,r,v) (_Add(l,v),_Add(r+1,-v))
inline int _Sum(int c[], int i){int r=0;for(;i;r+=c[i],i-=i&-i);return r;}
#define Sum(l,r) ((r+1)*(_Sum(c,r)-_Sum(c,l-1))-_Sum(s,r)+_Sum(s,l-1))

(以上代码以及以后的代码都完全没有考虑long long问题，实际使用的时候需要注意)。


3.树状数组上二分

接下来的部分都是本菜自己研究的，之前拿给ODT大佬(千古神犇nzhtl1477，数据结构碾压众生)看，还被嫌弃了。

ODT: 树状数组上二分是烂大街的trick吧


线段树上二分可以在必要的时候优化掉一个 $O(\log n)$ 的复杂度。想要用树状数组取代线段树是不可能缺少这一步的。

如图，在接下来的思考过程中，总是将树状数组当做去掉右儿子的线段树来思考。一个节点的父亲即其向上碰到的第一个存在的节点，而要注意一个节点的前驱并不是左儿子，比如很显然 $16$ 没有前驱，因为 $16-\text{lowbit}(16) = 16 - 16 = 0$ 。

实际上只需要标注一下二分时经过的点的路径就一目了然了。

即每次只需要在红色箭头所示的位置判断向左还是向右即可。因为一般情况下线段树二分也只用到了左儿子的值，因此这个方法可以轻松地拓展到树状数组上。

只需要能够找到左右儿子的指针即可: 这个可以自己YY，比如说一种可行的方法就是左儿子是p-((p&-p)>>1)而右儿子就是p+((p&-p)>>1)。然后就可以像线段树二分那样写了: F(*,k)表示要查询第一个和>=k的位置。

1
2
3
4
5
int c[R+5];
inline void Add(int i, int v){for(;i<=R;c[i]+=v,i+=i&-i);}
inline int Sum(int i){int r=0;for(;i;r+=c[i],i-=i&-i);return r;}
inline int F(int p, int k){return p&1 ? p<=R&&p+(c[p]<k)<=R?p+(c[p]<k):-1
                                      : p<=R&&c[p]<k?F(p+((p&-p)>>1),k-c[p]):F(p-((p&-p)>>1),k);}

首先加法和求和都是可以正常进行的。

F(p,k)的这一行代码(对，就是一行，只是因为放不下了才换行)其实是在说:

首先任何时候都要判断当前位置p是否在R以内，这个条件不满足的话，整个树状数组的和都是不够的，即没有满足答案的位置(或者认为满足答案的位置在 $\infty$ )，返回-1。注意即使保证存在合法位置，p<=R这个判断条件也不一定可以去掉，后文会解释。

如果当前已经二分到了一个奇数节点p，那么到达了边界，进行最后一次二分判断答案是p还是p+1即可。

否则，比较当前位置c[p]的值(树状数组二分的当前位置等价于线段树二分的左儿子位置)，就可以判断出是向左走p-((p&-p)>>1)还是向右走p+((p&-p)>>1)。

如果这个树状数组总值域长度R为 $2$ 的次幂，那么初始时直接查询F(R,k)就可以了，否则由于树状数组二分的当前位置等价于线段树二分的左儿子位置，所以初始传入的参数是小于等于R的最大的 $2$ 的次幂，即F(1<<ilogb(R),k)，但是这个时候树状数组大小至少要开 $\frac{3}{2} \cdot 2^{\text{ilogb}(R)}$大小，因为第一步可能会向右走。而有些时候p<=R这个条件不一定可以去掉也是因为有可能第一步太向右了，此后需要不断左转，但是这部分的和没有维护。当然，将值域放大为 $2$ 的次幂，增大一点点常数，可以轻松解决一切边界问题。


4.树状数组代替简单线段树

还是这个思路: 将树状数组当做去掉了右儿子的线段树。

如果想要树状数组代替线段树，那么就不可避免地要处理标记问题。这是非常头疼的。因为树状数组没有右儿子，下传标记会很爆炸。一个很好的解决办法就是标记永久化。

结合树状数组本身的要求，下文将给出一个树状数组代替线段树维护支持标记永久化的可减性信息的一般方法。


我将这个方法称为区间树状数组。

考虑线段树在标记永久化的时候，其实就是将其严格祖先所维护的和修改，然后在当前点打上一个标记。

树状数组的祖先和线段树的祖先是相同的，这一点不需要改变，而树状数组的祖先可以用迭代找父亲的i+(i&-i)操作快速求出。例如 $[1,14]$ 进行区间加，就需要修改 $14$ 和 $16$ 所维护的和。不需要修改 $15$ 的和，因为 $15$ 可以查询到 $14$ 的标记。

由于树状数组维护的节点都是前缀和而不是区间和，那么打标记的时候就要在所有前缀节点上打。例如 $[1,14]$ 进行区间加，那么就需要在 $8,12,14$ 上打标记，会发现这恰好是节点 $14$ 的前驱路径。

因此就得到区间加的方法: 如果要 $[l,r]$ 进行区间加可以拆分为 $[1,l-1]$ 区间减和 $[1,r]$ 区间加。而对于 $[1,r]$ 区间加，先将r的父亲的祖先路径值修改(注意不是r的祖先路径，这条路径应该不包括r本身)，然后将r的前驱路径打永久化标记。

查询的时候类似: 查询 $[1,r]$ 的和，就是先直接树状数组查询前缀和(r的前驱路径)，然后再统计其r的父亲的祖先路径对其的贡献。

1
2
3
4
5
6
7
8
int z[MAXN+5], c[MAXN+5];
inline void _Add(int R, int v){for(rint r=R;r;z[r]+=v,c[r]+=(r&-r)*v,r-=r&-r);
                               for(rint r=R+(R&-R),l;r<=MAXN;l=r-(r&-r),c[r]+=(R-l)*v,r+=r&-r);}
inline int _Sum(int R){int _=0;for(rint r=R;r;_+=c[r],r-=r&-r);
                               for(rint r=R+(R&-R),l;r<=MAXN;l=r-(r&-r),_+=(R-l)*z[r],r+=r&-r);
                               return _;}
#define Add(l,r,v) (_Add(r,v),l>1?_Add(l-1,-v),0:0)
#define Sum(l,r) (_Sum(r)-(l>1?_Sum(l-1):0))

(是的，它们本来就是每个函数都是一行，放不下了才换行的)

c[]表示维护和的数组，z[]表示永久化标记数组。

每次修改的时候，第一行将前驱路径打了标记；第二行将r的父亲的祖先路径值修改。

每次查询的时候，第一行查询前驱路径的和，和正常树状数组查询一样；第二行处理r的父亲的祖先路径上所有永久化标记的贡献。对于一个区间 $(l,r]$ ，贡献自然是 $(r-l) \cdot \text{z}[r]$ 。

注意因为无论在修改还是在查询中都访问了双向的路径(祖先路径和前驱路径)，因此要特别处理下标 $0$ 的问题。


之前提到了这个方法可以一般化的维护支持标记永久化的可减性信息。我们来看一个使用的例子。

Codeforces 316 E3

题目大意: 维护序列a[]，支持单点修改，区间加，或查询区间 $[l,r]$ 的:

其中 $F$ 为斐波那契数列。 $n,q \le 2 \times 10^5$ 。

首先，假如模数是 $10^9+7$ 就很简单了: 将斐波那契数列用通项公式看成等比数列，然后相当于区间加等比数列维护区间和。线段树维护即可。一种常数比较小的做法是直接维护 $\sum a_i\phi^i$ 而无视查询区间，最后查询出区间和以后再同一除以 $\phi^{l-1}$ 即可。

现在模数是 $10^9$ ，不仅 $\phi$ 不存在，而且不能做除法。考虑将斐波那契看成矩阵，维护 $\sum a_iA^i$ ，这时候: 因为矩阵 $A$ 的逆是存在的，所以就可以用上述方法维护了。

注意到更新节点信息的时候不能用等比数列求和公式了，因为 $A-I$ 的逆不存在。不过可以直接用分块矩阵 $(S \vert A)$ 倍增求出 $I+A+A^2+…+A^k$ ，进而求出区间和。

除了采用区间树状数组以外，我还采用了另一个Trick来优化这道题: 因为斐波那契矩阵及其次幂都是关于主对角线对称的，因此只需要维护一个二元组就可以表达其全部信息。具体运算如下:


代码风格鬼畜(不如直接去Codeforces看提交记录):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200000
#define MOD 1000000000
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define mid ((lef+rig)>>1)
#define Fib(L,R) (U[(R)+2]-U[(L)+1])
#define rint register int
#define gc() getchar()
inline int read(int r=0,int s=0,int c=gc()){for(;c<48||c>57;s=c,c=gc());for(;c>=48&&c<=57;(r*=10)+=c-48,c=gc());return s^'-'?r:-r;}
struct F
{
    int x,y; F(){} F(int a){x=y=a;} F(int _x, int _y){x=_x,y=_y;} inline F operator * (F b){return F((1ll*x*b.x+1ll*y*b.y)%MOD,(1ll*y*b.x+1ll*b.y*(x+MOD-y))%MOD);}
    inline F&operator +=(F b){return *this=F((x+b.x)%MOD,(y+b.y)%MOD);} inline F operator + (F b){return F((x+b.x)%MOD,(y+b.y)%MOD);} inline F operator - (F b){return F((x+MOD-b.x)%MOD,(y+MOD-b.y)%MOD);} 
}f[MAXN+5], U[MAXN+5], E[MAXN+5]; int c[MAXN+5], n, m; inline F operator * (int k, F a){return F(1ll*k*a.x%MOD,1ll*k*a.y%MOD);}
inline void Add(int &x, int v){(x+=v)<MOD?:x-=MOD;} inline void ED(int p, int k){static F _; _ = k*U[p]; for(rint r = p; r <= n; f[r] += _, r += r&-r);}
inline void AD(int p, int k){if(!p) return; for(rint r = p, l; r; l = r-(r&-r), Add(c[r],k), f[r] += k*Fib(l+1,r), r = l); for(rint r = p+(p&-p), l; r <= n; l = r-(r&-r), f[r] += k*Fib(l+1,p), r += r&-r);}
inline F QU(int p){if(!p) return 0; static F _; _ = F(0,0); for(rint r = p; r; _ += f[r], r -= r&-r); for(rint r = p+(p&-p), l; r <= n; l = r-(r&-r), _ += c[r]*Fib(l+1,p), r += r&-r); return _;}
int main()
{
    n = read(), m = read(), U[0] = F(1,0), U[1] = F(1,1); for(rint i = 2; i <= n+2; U[i] = U[i-1]*U[1], i++);
    E[0] = F(1,0), E[1] = F(0,1); for(rint i = 2; i <= n+2; E[i] = E[i-1]*E[1], i++); for(rint i = 1; i <= n; ED(i,read()), i++);
    for(rint o, l, r, x; m--; ) switch(read())
    {
        case 1: l = read(), ED(l,(read()+MOD-((QU(l)-QU(l-1))*E[l]).x)%MOD); break;
        case 2: l = read(), r = read(), printf("%d\n",((QU(r)-QU(l-1))*E[l]).x); break;
        case 3: l = read(), r = read(), x = read(), AD(r,x), AD(l-1,MOD-x); break;
    }   return 0;
}


采用了这两个常数优化以后，我的代码目前为止依然在此题Codeforces上排名第一。(Landia是我的小号之一，第一名那位小哥是抄了我的代码但是不知道为啥比我跑得快，vjudge2和vjudge5的提交也都是我提交的)。

大家也可以在我的OI资源分享中找到这道题的代码和题解。


5.树状数组代替一般线段树

这个有点假。因为上文提到过

如果想要树状数组代替线段树，那么就不可避免地要处理标记问题。这是非常头疼的。因为树状数组没有右儿子，下传标记会很爆炸。

然而这个爆炸指的是增加一个 $O(\log n)$ 的复杂度，即每次下传标记的时候直接下传给 $O(\log n)$ 个儿子。

于是我们成功的得到了一个比线段树优秀一个2到4的常数但慢一个log的优秀做法啦！

迄今为止尚未发现有什么卵用。


6.可持久化树状数组

咳咳。如果想要树状数组代替线段树，那么就不可避免地要处理可持久化问题。

注意到在4.树状数组代替简单线段树的代码中，只用到了前驱路径和祖先路径，那么是不是只需要用指针(或数组指针)将每个节点的前驱和父亲记录下来就好了呢？没有仔细思考过是否可行，自然也没有实现过以判断常数是否确实更优。

这个问题就留给读者自己思考


UPD 2018.09.01:

仔细思考一下，会发现一个问题在于查询的随机访问: 就是如何快速得到第 $i$ 个版本中位置为 $j$ 的节点。

可以用fat node的方法: 将位置 $j$ 的所有历史版本存在一个vector里。查找的时候二分查找前驱和后继。但如果每次操作每个节点都二分是 $O(\log^2n)$ 的。

咨询了ODT大佬(千古神犇nzhtl1477，数据结构碾压众生)一下:

具体做法咕了。


7.某例题

我们来做一道没有出处、没有std、没有数据的口胡题目看一看:

树状数组代替平衡树

题目大意: 支持在一个multiset中插入一段连续的自然数数列 $l,l+1,l+2,…,r$ 、或查询前 $k$ 小数字的和(自然溢出)。保证所有数字不超过一个不是太大的给定值 $R$ ，数据范围为数据结构经典范围乘上一个没测过不知道是多大的常数。

显然有 $3$ 种做法:

  1. 平衡树拆点 + 平衡树上二分
  2. 线段树维护区间加等差数列 + 线段树上二分
  3. 区间树状数组维护区间加等比数列 + 树状数组上二分


8.总结

上文中，简单介绍了: 树状数组的基本使用方法，树状数组下标平移和反转技巧，树状数组清零技巧，树状数组与差分的结合(包括区间加单点查询以及区间加区间查询)，树状数组上二分，树状数组代替简单线段树。没有探讨并简单探讨了关于树状数组进一步代替线段树和树状数组可持久化的问题，给读者留下了思考空间。

树状数组代替简单线段树是本文主要表达的部分，再次强调其可以解决的是维护支持标记永久化的可减性信息。


(完结撒花)


扫描二维码即可在手机上查看这篇文章，或者转发二维码来分享这篇文章:


文章作者: Magolor
文章链接: https://magolor.cn/2018/08/27/2018-08-27-blog-01/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Magolor！
OI资源树状数组黑科技
扫描二维码在手机上查看或转发二维码以分享Magolor的博客