树状数组的新构想

（一篇没啥用的博客） # 前言 由于本人对于树状数组有着特殊的情感(doge)，故经过一番思索，想出一种类似于线段树的树状数组，并发此水文。刚学树状数组的时候，我只知道树状数组可以单点修改，用来求前缀和，并由此延伸至区间和。后来学了差分，我又明白树状数组可以用来区间修改+单点查询及区间修改+区间查询（修改仅限加减法，乘除法不行）。看了Chanis大佬的文章[可以代替线段树的树状数组？](https://www.luogu.com.cn/blog/Chanis/super-BIT) 后，我掌握了树状数组求区间最值的方法。 但令我深感麻烦的是，以上几种功能往往不能组合在一起，而且区间修改仅限加减法使得树状数组具有很大的局限性，区间修改+区间查询的公式又过于复杂，很难记住。 那么，是否可以模仿线段树，想出一种带有懒标记的树状数组呢？这便是这篇文章的主题了。 # 基本结构 我们先看看树状数组的结构：  观察结构我们可以获得以下特性： 1.设有一结点，序号为e。那么该结点的子结点必然是e-1,e-2,e-4,e-8...（减数小于lowbit(e)）。 例如C[2]的子结点是C[2-1]即C[1]，C[8]的子结点是C[8-1],C[8-2],C[8-4]。 因此我们可以用一个for循环遍历它的子结点。同时，这个结点所包括的区间就是从e-lowbit(e)+1到e这个区间。 ```c for (int x=1;x<lowbit(e);x<<=1) ``` 2.与线段树不同，线段树有一个“顶点”，是整个线段树的根节点，寻求区间可以从顶点逐步向下寻找。但树状数组不一定是一棵树，它可以是多棵树（比如你把上图的C[8]结点删掉看看会长啥样），因此不满足这一特性。所以用树状数组查找区间时，必须将所有根结点都遍历一遍。 有了这些特性，我们就以P3372线段树1为例题进行探讨。 首先得声明一个树状数组。为了实现懒标记，我们用结构体进行声明： ```c typedef struct { ll sum,zhi,lazy;//sum即该结点所包含区间之和，zhi为该结点本身的数值，lazy为懒标记。 }hh; hh t[100005]; ``` 值得注意的是之所以要设一个变量存数值，是因为单个的结点数值在线段树中用最底层的结点存储，而这种树状数组的一个结点不仅要存它所管辖的区间和，还要存它本身的数值。 说实话，当我用结构体进行声明时，我就感觉这个树状数组已经不再是一个真正的树状数组了。。。 然后我们要将题目所给的数值输入进去，即： ```c void add(ll w,ll l) { for (int x=l;x<=n;x+=(x&(-x))) t[x].sum+=w; } ``` 主函数内 ```c for (ll x=1;x<=n;x++) { scanf("%lld",&t[x].zhi); add(t[x].zhi,x); } ``` 然后就剩下区间修改和区间查询的问题了。 区间修改我们可以这样实现。我们先从最高的结点开始遍历，逐步递归： 1.如果该结点所包含的区间被包含在题目所给的区间内，就直接更新区间和、该结点本身的值及懒标记，再返回更新后的区间和。 2.如果存在交集但并不包含，就先下传懒标记，并遍历该结点的所有子结点，对它们进行递归，将它们返回的区间和累加起来，作为该结点更新后的区间和。同时还要特判如果该结点也在题目要求的区间内，则更新该点的数值。最后返回更新后的区间和。 3.如果不存在交集，则返回原区间和。 结合上面那张结构图，我们假设处理一串长度为7（请将图中的C[8]省略）的数列，以将3-6区间内每个数加1为例： 此时树状数组有3个根结点，分别是C[4],C[6],C[7]（如果数列长度为8的话，C[8]就能把它们全部包含进去），它们没有父结点，所以是根节点。 用一个循环，将它们分别递归： ```c for (ll x=n;x>0;x-=(x&(-x))) insert(k,xi,yi,x); ``` 然后我们追踪它递归的过程。 1.当递归到C[7]时（代码中是t[7]），我们发现lowbit（7）=1，所以C[7]结点的左边界就是7-lowbit（7）+1=7，也就是说C[7]结点管辖的区间（7-7）与题目要求的区间（3-6）无交集，直接return。 2.当递归到C[6]时（代码中是t[6]），我们发现lowbit（6）=2，所以C[6]结点的左边界就是6-lowbit（6）+1=5，也就是说C[6]结点管辖的区间（5-6）被完全包含在题目所给的区间（3-6）中，而lowbit（6）=2就是C[6]管辖的区间中的元素数量，所以我们将C[6]的sum加上1乘lowbit（6），lazy和zhi分别加上1，直接return。 3.当递归到C[4]时（代码中是t[4]），我们发现lowbit（4）=4，所以C[4]结点的左边界就是4-lowbit（4）+1=1，也就是说C[4]结点管辖的区间（1-4）与题目给的区间（3-6）有交集，但不完全包含，于是我们先特判C[4]的数值是否在区间内，那么4当然是在3-6之间的，所以我们把C[4]的zhi加1。然后我们把C[4]的sum赋值为C[4]的zhi，并遍历+递归它的各子结点，将它们返回的区间和加进sum，作为sum的更新值。以下为子结点的递归。 3-1.当递归到C[3]时，其管辖的区间完全包含在（3-6）中，因此更新它的sum，lazy和zhi，并返回sum。 3-2.当递归到C[2]时，其管辖的区间（1-2）与（3-6）无交集，不需更改，因此直接返回原sum。 代码如下： ```c ll insert(ll w,ll l,ll r,ll e)//w是要加的数值，l和r是题目给出的区间，e是当前递归到的树状数组结点。 { ll left=e-(e&(-e))+1,f=e&(-e);//求左边界left，用f存储lowbit(e)，e本身就是区间的右边界。 if (left>r||e<l) return t[e].sum;//如果无交集，直接返回原区间和。 if (left>=l&&e<=r) { t[e].lazy+=w; t[e].sum+=(e-left+1)*w; t[e].zhi+=w; return t[e].sum;//题目要求的区间包含该结点的区间，更新懒标记，区间和及数值，返回更新后的区间和。 } if (e>=l&&e<=r) t[e].zhi+=w;//特判如果结点在题目要求的区间内，更新数值。 t[e].sum=t[e].zhi;//先将区间和赋成该结点数值。 pushdown(e);//下传懒标记。 for (ll x=1;x<f;x<<=1) t[e].sum+=insert(w,l,r,e-x);//累加各子结点区间和。 return t[e].sum;//返回更新后的区间和。 } ``` 懒标记是这样下传的： ```c void pushdown(ll e) { if ((e&(-e))>1&&t[e].lazy!=0)//当该结点不是最底层的结点且懒标记不为0时。 { ll up=e&(-e);//用up记录lowbit(e)。 for (ll x=1;x<up;x<<=1) { ll f=e-x,fe;//用f表示子结点，fe表示子结点的lowbit。 fe=(f&(-f)); t[f].sum+=fe*t[e].lazy; t[f].lazy+=t[e].lazy; t[f].zhi+=t[e].lazy; } t[e].lazy=0; } } ``` 最后便是区间查询了。 1.如果包含，直接返回区间和。 2.交集但不包含，依次递归子结点并累加区间和，再特判是否需要加上该结点数值，最后返回区间和。 3.无交集则返回0。 关于举例子可以参考上面区间修改的例子，只是无交集的时候，区间修改要返回原sum，而区间查询要返回0。 代码如下： ```c ll query(ll l,ll r,ll e) { ll left=e-(e&(-e))+1,f=(e&(-e)); if (left>r||e<l) return 0; pushdown(e); if (left>=l&&e<=r) return t[e].sum; ll summ=0; if (e>=l&&e<=r) summ+=t[e].zhi; for (ll x=1;x<f;x<<=1) summ+=query(l,r,e-x); return summ; } ``` 再贴完整代码： ```c #include<stdio.h> #include<stdlib.h> #include<string.h> #include<stdarg.h> #include<ctype.h> typedef long long ll; ll n,m,xi,yi,k,c; typedef struct { ll sum,zhi,lazy;//sum即该结点所包含区间之和，zhi为该结点本身的数值，lazy为懒标记。 }hh; hh t[100005]; void add(ll w,ll l) { for (int x=l;x<=n;x+=(x&(-x))) t[x].sum+=w; } void pushdown(ll e) { if ((e&(-e))>1&&t[e].lazy!=0) { ll up=e&(-e); for (ll x=1;x<up;x<<=1) { ll f=e-x,fe; fe=(f&(-f)); t[f].sum+=fe*t[e].lazy; t[f].lazy+=t[e].lazy; t[f].zhi+=t[e].lazy; } t[e].lazy=0; } } ll insert(ll w,ll l,ll r,ll e) { ll left=e-(e&(-e))+1,f=e&(-e);//求左边界left，用f存储lowbit(e)，e本身就是区间的右边界。 if (left>r||e<l) return t[e].sum;//如果无交集，直接返回原区间和。 if (left>=l&&e<=r) { t[e].lazy+=w; t[e].sum+=(e-left+1)*w; t[e].zhi+=w; return t[e].sum;//题目要求的区间包含该结点的区间，更新懒标记，区间和及数值，返回更新后的区间和。 } if (e>=l&&e<=r) t[e].zhi+=w;//特判如果结点在题目要求的区间内，更新数值。 t[e].sum=t[e].zhi;//先将区间和赋成该结点数值。 pushdown(e);//下传懒标记。 for (ll x=1;x<f;x<<=1) t[e].sum+=insert(w,l,r,e-x);//累加各子结点区间和。 return t[e].sum;//返回更新后的区间和。 } ll query(ll l,ll r,ll e) { ll left=e-(e&(-e))+1,f=(e&(-e)); if (left>r||e<l) return 0; pushdown(e); if (left>=l&&e<=r) return t[e].sum; ll summ=0; if (e>=l&&e<=r) summ+=t[e].zhi; for (ll x=1;x<f;x<<=1) summ+=query(l,r,e-x); return summ; } int main(void) { scanf("%lld%lld",&n,&m); for (ll x=1;x<=n;x++) { scanf("%lld",&t[x].zhi); add(t[x].zhi,x); } for (ll x=1;x<=m;x++) { scanf("%lld%lld%lld",&c,&xi,&yi); if (c==1) { scanf("%lld",&k); for (ll x=n;x>0;x-=(x&(-x))) insert(k,xi,yi,x); } else { ll summ=0; for (ll x=n;x>0;x-=(x&(-x))) summ+=query(xi,yi,x); printf("%lld\n",summ); } } return 0; } ``` # 乘法范围的区间修改+区间查询 当然，如果只有加减法范围内的区间修改和区间查询，则完全可以用差分公式来解决。 但如果有乘法的区间修改和区间查询呢？这便是P2023维护序列的问题了。这题无法使用差分公式，只能用以上的那种类似于线段树的树状数组。上代码： ```c #include<stdio.h> #include<stdlib.h> #include<string.h> #include<stdarg.h> #include<ctype.h> #define lowbit(e) (e&(-e)) typedef long long ll; int n,ch,t,g,m; ll p,c; typedef struct { ll sum,zhi,chen,lzy; }hh; hh a[100005]; void add(int w,int l) { a[l].sum=w%p;a[l].chen=1; int r=lowbit(l); for (int x=1;x<r;x<<=1) a[l].sum=(a[l].sum+a[l-x].sum)%p; } void pushdown(int w) { int up=lowbit(w); if (w>1) { for (int x=1;x<up;x<<=1) { int f=lowbit((w-x)); a[w-x].sum=(a[w-x].sum*a[w].chen+a[w].lzy*f)%p; a[w-x].zhi=(a[w-x].zhi*a[w].chen+a[w].lzy)%p; a[w-x].lzy=(a[w-x].lzy*a[w].chen+a[w].lzy)%p; a[w-x].chen=(a[w-x].chen*a[w].chen)%p; } a[w].lzy=0;a[w].chen=1; } } ll cheng(ll w,int l,int r,int e) { int left=e-lowbit(e)+1,up=lowbit(e); if (left>r||e<l) { return a[e].sum; } if (left>=l&&e<=r) { a[e].sum=(a[e].sum*w)%p; a[e].zhi=(a[e].zhi*w)%p; a[e].chen=(a[e].chen*w)%p; a[e].lzy=(a[e].lzy*w)%p; return a[e].sum; } pushdown(e); if (e>=l&&e<=r) a[e].zhi=(a[e].zhi*w)%p; a[e].sum=a[e].zhi; for (int x=1;x<up;x<<=1) { a[e].sum+=cheng(w,l,r,e-x); a[e].sum%=p; } return a[e].sum; } ll insert(ll w,int l,int r,int e) { int left=e-lowbit(e)+1,up=lowbit(e); if (left>r||e<l) { return a[e].sum; } if (left>=l&&e<=r) { a[e].sum=(a[e].sum+(e-left+1)*w)%p; a[e].zhi=(a[e].zhi+w)%p; a[e].lzy=(a[e].lzy+w)%p; return a[e].sum; } pushdown(e); if (e>=l&&e<=r) a[e].zhi=(a[e].zhi+w)%p; a[e].sum=a[e].zhi; for (int x=1;x<up;x<<=1) { a[e].sum+=insert(w,l,r,e-x); a[e].sum%=p; } return a[e].sum; } ll query(int l,int r,int e) { int left=e-lowbit(e)+1,up=lowbit(e); if (left>r||e<l) { return 0; } if (left>=l&&e<=r) { return a[e].sum; } pushdown(e); ll summ=0; if (e>=l&&e<=r) summ+=a[e].zhi; for (int x=1;x<up;x<<=1) { summ+=query(l,r,e-x); summ%=p; } return summ; } int main(void) { scanf("%d%lld",&n,&p); for (int x=1;x<=n;x++) { scanf("%lld",&a[x].zhi); add(a[x].zhi,x); } scanf("%d",&m); for (int x=1;x<=m;x++) { scanf("%d%d%d",&ch,&t,&g); if (ch==1) { scanf("%lld",&c); for (int y=n;y>0;y-=lowbit(y)) cheng(c,t,g,y); } else if (ch==2) { scanf("%lld",&c); for (int y=n;y>0;y-=lowbit(y)) insert(c,t,g,y); } else if (ch==3) { ll summ=0; for (int y=n;y>0;y-=lowbit(y)) summ=(summ+query(t,g,y))%p; printf("%lld\n",summ); } } return 0; } ``` # 其它类型：区间平方和 还有P1471方差这道题，考到了区间修改、区间和与区间平方和，做法贴在下面： ```c #include<stdio.h> #include<stdlib.h> #include<string.h> #include<stdarg.h> #include<ctype.h> #define lowbit(e) (e&(-e)) int n,m,ch; double xi,yi,k; typedef struct { double sum,ping,zhi,lzy; }hh; hh c[100005]; void add(int w,double l) { int up=lowbit(w); c[w].sum=l; c[w].ping=l*l; for (register int x=1;x<up;x<<=1) { c[w].sum+=c[w-x].sum; c[w].ping+=c[w-x].ping; } } void pushdown(int e) { int up=lowbit(e); if (up>1&&c[e].lzy!=0) { for (register int x=1;x<up;x<<=1) { c[e-x].ping+=2*c[e-x].sum*c[e].lzy+lowbit((e-x))*c[e].lzy*c[e].lzy; c[e-x].zhi+=c[e].lzy; c[e-x].sum+=c[e].lzy*lowbit((e-x)); c[e-x].lzy+=c[e].lzy; } c[e].lzy=0; } } void insert(double w,int l,int r,int e) { int up=lowbit(e),left=e-lowbit(e)+1; if (left>r||e<l) return; if (left>=l&&e<=r) { c[e].ping+=2*c[e].sum*w+lowbit(e)*w*w; c[e].lzy+=w; c[e].sum+=w*lowbit(e); c[e].zhi+=w; return; } pushdown(e); if (e>=l&&e<=r) c[e].zhi+=w; c[e].sum=c[e].zhi; c[e].ping=c[e].zhi*c[e].zhi; for (register int x=1;x<up;x<<=1) { insert(w,l,r,e-x); c[e].sum+=c[e-x].sum; c[e].ping+=c[e-x].ping; } } double getsum(int l,int r,int e) { int up=lowbit(e),left=e-lowbit(e)+1; if (left>r||e<l) return 0; if (left>=l&&e<=r) return c[e].sum; pushdown(e); double summ=0; if (e>=l&&e<=r) summ+=c[e].zhi; for (register int x=1;x<up;x<<=1) summ+=getsum(l,r,e-x); return summ; } double query(double w,int l,int r,int e) { int up=lowbit(e),left=e-lowbit(e)+1; if (left>r||e<l) return 0; if (left>=l&&e<=r) return c[e].ping; pushdown(e); double summ=0; if (e>=l&&e<=r) summ+=c[e].zhi*c[e].zhi; for (register int x=1;x<up;x<<=1) summ+=query(w,l,r,e-x); return summ; } int main(void) { scanf("%d%d",&n,&m); for (register int x=1;x<=n;x++) { scanf("%lf",&c[x].zhi); add(x,c[x].zhi); } for (register int x=1;x<=m;x++) { scanf("%d%lf%lf",&ch,&xi,&yi); if (ch==1) { scanf("%lf",&k); for (register int x=n;x>0;x-=lowbit(x)) insert(k,xi,yi,x); } else if (ch==2) { double summ=0; for (register int x=n;x>0;x-=lowbit(x)) summ+=getsum(xi,yi,x); printf("%.4lf\n",summ/(yi-xi+1)); } else { double fangcha=0,summ=0; for (register int x=n;x>0;x-=lowbit(x)) summ+=getsum(xi,yi,x); summ/=yi-xi+1; for (register int x=n;x>0;x-=lowbit(x)) fangcha+=query(summ,xi,yi,x); fangcha/=yi-xi+1; fangcha-=summ*summ; printf("%.4lf\n",fangcha); } } return 0; } ``` （看了这么多代码，应该能明白我是个C党了吧（逃）） # 时间复杂度分析 可以看出，当我们修改/查询一次时，最坏情况要递归log n层，每层要循环log n次，所以单次修改/查询的时间复杂度为O((log n)^2)，同理，修改/查询n次的时间复杂度就是O(n (log n)^2)，高于线段树的O(n log n)。 当我提交的时候，它的耗时是线段树做法的2-3倍，内存占用量是线段树做法的二分之一到六分之一不等，可以说，这是一种“时间换空间”的做法。 #### 但考虑到考试中对于时间复杂度的要求很高，但对于空间复杂度的要求较为宽松，因此考试中更推荐用线段树。本文仅作为证明树状数组能够实现线段树功能的一篇文章，无太大实用价值，仅供参考。 ```c //【完】 ```