树状数组的新构想
Souhara_Hisetsu · · 个人记录
（一篇没啥用的博客）
前言
由于本人对于树状数组有着特殊的情感(doge)，故经过一番思索，想出一种类似于线段树的树状数组，并发此水文。刚学树状数组的时候，我只知道树状数组可以单点修改，用来求前缀和，并由此延伸至区间和。后来学了差分，我又明白树状数组可以用来区间修改+单点查询及区间修改+区间查询（修改仅限加减法，乘除法不行）。看了Chanis大佬的文章可以代替线段树的树状数组？ 后，我掌握了树状数组求区间最值的方法。
但令我深感麻烦的是，以上几种功能往往不能组合在一起，而且区间修改仅限加减法使得树状数组具有很大的局限性，区间修改+区间查询的公式又过于复杂，很难记住。
那么，是否可以模仿线段树，想出一种带有懒标记的树状数组呢？这便是这篇文章的主题了。
基本结构
我们先看看树状数组的结构：
观察结构我们可以获得以下特性：
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这个区间。
for (int x=1;x<lowbit(e);x<<=1)2.与线段树不同，线段树有一个“顶点”，是整个线段树的根节点，寻求区间可以从顶点逐步向下寻找。但树状数组不一定是一棵树，它可以是多棵树（比如你把上图的C[8]结点删掉看看会长啥样），因此不满足这一特性。所以用树状数组查找区间时，必须将所有根结点都遍历一遍。
有了这些特性，我们就以P3372线段树1为例题进行探讨。
首先得声明一个树状数组。为了实现懒标记，我们用结构体进行声明：
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;
}主函数内
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]就能把它们全部包含进去），它们没有父结点，所以是根节点。
用一个循环，将它们分别递归：
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。
代码如下：
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;//返回更新后的区间和。
}懒标记是这样下传的：
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。
代码如下：
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;
}再贴完整代码：
#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维护序列的问题了。这题无法使用差分公式，只能用以上的那种类似于线段树的树状数组。上代码：
#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方差这道题，考到了区间修改、区间和与区间平方和，做法贴在下面：
#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倍，内存占用量是线段树做法的二分之一到六分之一不等，可以说，这是一种“时间换空间”的做法。
但考虑到考试中对于时间复杂度的要求很高，但对于空间复杂度的要求较为宽松，因此考试中更推荐用线段树。本文仅作为证明树状数组能够实现线段树功能的一篇文章，无太大实用价值，仅供参考。
//【完】