当前位置:首页 >> 学科竞赛 >>

树状数组维护区间和的模型及其拓广的简单总结


树状数组维护区间和的模型及其拓广的简单总结
by wyl8899 树状数组的基本知识已经被讲到烂了,我就不多说了,下面直接给出基本操作的代码。 假定原数组为 a[1..n],树状数组 b[1..n],考虑灵活性的需要,代码使用 int *a 传数组。 #define lowbit(x) ((x)&(-(x))) int sum(int *a,int x){ in

t s=0; for(;x;x-=lowbit(x))s+=a[x]; return s; } void update(int *a,int x,int w){ for(;x<=n;x+=lowbit(x))a[x]+=w; } sum(x)返回原数组[1,x]的区间和,update(x,w)将原数组下标为 x 的数加上 w。 这两个函数使用 O(操作数*logn)的时间和 O(n)的空间完成单点加减,区间求和的功能。 接下来做一些升级,让树状数组完成区间加减,单点查询的功能。 直接做的话很困难,需要对问题做一些转化。 考虑将原数组差分,即令 d[i]=a[i]-a[i-1],特别地,d[1]=a[1]。 此时 a[i]=d[1]+..+d[i],所以单点查询 a[i]实际上就是在求 d 数组的[1..i]区间和。 而区间[l,r]整体加上 k 的操作,可以简单地使用 d[l]+=k 和 d[r+1]-=k 来完成。 于是,我们用树状数组来维护 d[],就可以解决问题了。 下面再升级一次,完成区间加减,区间求和的功能。 仍然沿用 d 数组,考虑 a 数组[1,x]区间和的计算。d[1]被累加了 x 次,d[2]被累加了 x-1 次,...,d[x]被累加了 1 次。 因此得到 sigma(a[i]) =sigma{d[i]*(x-i+1)} =sigma{ d[i]*(x+1) - d[i]*i } =(x+1)*sigma(d[i])-sigma(d[i]*i) 所以我们再用树状数组维护一个数组 d2[i]=d[i]*i,即可完成任务。 POJ 3468 就是这个功能的裸题,下面给出代码。 [请注意我们上面的讨论都假定了 a[]初始全是 0。如果不是这样呢?下面的程序里给出了一 个相对简便的处理办法。] // POJ 3468 Using BIT #include <cstdio> const int maxn=100010; __int64 a[maxn],b[maxn],c[maxn]; int n,m;

inline int lowbit(const int &x){ return x&(-x); } __int64 query(__int64 *a,int x){ __int64 sum=0; while(x){sum+=a[x];x-=lowbit(x);} return sum; } void update(__int64 *a,int x,__int64 w){ while(x<=n){a[x]+=w;x+=lowbit(x);} } int main(){ int l,r,i; __int64 ans,w; char ch; scanf("%d%d",&n,&m); a[0]=0; for(i=1;i<=n;++i){ scanf("%I64d",&a[i]); a[i]+=a[i-1]; } while(m--){ scanf("%c",&ch); while(ch!='Q' && ch!='C')scanf("%c",&ch); if(ch=='Q'){ scanf("%d%d",&l,&r); ans=a[r]-a[l-1]+(r+1)*query(b,r)-l*query(b,l-1)-query(c,r)+query(c,l-1); printf("%I64d\n",ans); }else{ scanf("%d%d%I64d",&l,&r,&w); update(b,l,w); update(b,r+1,-w); update(c,l,w*l); update(c,r+1,-(r+1)*w); } } return 0; } [当 a[]初始不全 0 的时候,我们就只维护后来加上去的部分,查询区间和的时候再补上初 始的时候这一段的区间和就可以了。]

======================一维到二维的分割线========================= 接下来到二维树状数组。 先看看 sum 和 update 变成什么样子了吧。 inline int gs(int a[maxn][maxn],int x,int y){ int s=0,t; for(;x;x-=lowbit(x)) for(t=y;t;t-=lowbit(t)) s+=a[x][t]; return s; } inline void gp(int a[maxn][maxn],int x,int y,int w){ int t; for(;x<=n;x+=lowbit(x)) for(t=y;t<=m;t+=lowbit(t)) a[x][t]+=w; } gs 就是 sum,gp 就是 update,由于需要多次调用的缘故,改成了更短的名字。 单点加减,矩形求和并不难,直接用上面的两段就行了。 需要注意的是矩形的求和怎么求。上面的代码返回的是(1,1)-(x,y)矩形的和。 那么(x1,y1)-(x2,y2)的矩形和由下式给出: sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1) 画个图就很好理解了。 对于涉及矩形加减的情形, 我们发现一维中的差分的办法在二维的情况用不出来, 所以要改 一下。思考一下一维中的差分的另外一个含义:d[i]同时也表示 d[i..n]的整体增量, d[i]+=k 就意味着把 d[i]..d[n]全部加上了 k。理解了之后就发现这个意义上可以推广到二 维,仍假设原矩形初始全为 0,以便接下来的叙述。 令 a[x,y]表示(x,y)-(n,m)矩形的整体增量,其中(n,m)是边界。 那么(x1,y1)-(x2,y2)矩形整体加 k 的代码就是 gp(a,x1,y1,w); gp(a,x2+1,y1,-w);gp(a,x1,y2+1,-w); gp(a,x2+1,y2+1,w); 仍然是建议画个图来帮助理解。 至此,矩形加减,单点查询的问题得到了解决。 重头戏在这里,矩形加减,矩形求和。 求原矩形(1,1)-(x,y)的和,结果由下式给出 sigma(i=1..x,j=1..y) a[i,j]*(x-i+1)*(y-j+1) 很好理解吧? 但是这个式子并不是那么容易求和的,展开一下求和的部分得到 a[i,j]* ( (x+1)(y+1) - (x+1)*j - (y+1)*x + i*j ) 整个式子就是 (x+1)(y+1)sigma(a[i,j]) - (x+1)sigma(a[i,j]*j) - (y+1)sigma(a[i,j]*i) + sigma(a[i,j]*i*j) 知道怎么处理了吧?如果没有请回去复习一维的处理方法。 令 b[i,j]=a[i,j]*i c[i,j]=a[i,j]*j d[i,j]=a[i,j]*i*j

维护 a,b,c,d 一共四个二维树状数组,问题得到解决。 tyvj p1716 就是实现这两个功能的裸题,下面给出完整代码。 // tyvj p1716 using 2D BIT #include<cstdio> #include<cstring> #define lowbit(x) ((x)&(-(x))) const int maxn=2049; int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn],d[maxn][maxn]; int n,m; inline int gs(int a[maxn][maxn],int x,int y){ int s=0,t; for(;x;x-=lowbit(x)) for(t=y;t;t-=lowbit(t)) s+=a[x][t]; return s; } inline void gp(int a[maxn][maxn],int x,int y,int w){ int t; for(;x<=n;x+=lowbit(x)) for(t=y;t<=m;t+=lowbit(t)) a[x][t]+=w; } inline int sum(int x,int y){ return (x+1)*(y+1)*gs(a,x,y)-(y+1)*gs(b,x,y)-(x+1)*gs(c,x,y)+gs(d,x,y); } inline void update(int x1,int y1,int x2,int y2,int w){ gp(a,x1,y1,w); gp(a,x2+1,y1,-w); gp(a,x1,y2+1,-w); gp(a,x2+1,y2+1,w); gp(b,x1,y1,w*x1); gp(b,x2+1,y1,-w*(x2+1)); gp(b,x1,y2+1,-w*x1); gp(b,x2+1,y2+1,w*(x2+1)); gp(c,x1,y1,w*y1); gp(c,x2+1,y1,-w*y1); gp(c,x1,y2+1,-w*(y2+1)); gp(c,x2+1,y2+1,w*(y2+1)); gp(d,x1,y1,w*x1*y1); gp(d,x2+1,y1,-w*(x2+1)*y1); gp(d,x1,y2+1,-w*x1*(y2+1)); gp(d,x2+1,y2+1,w*(x2+1)*(y2+1)); } int main(){ int x1,y1,x2,y2,w; char ch; scanf("%c",&ch); while(ch!='X')scanf("%c",&ch); scanf("%d%d\n",&n,&m);

memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); while(scanf("%c",&ch)!=EOF){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(ch=='L'){ scanf("%d\n",&w); update(x1,y1,x2,y2,w); }else{ scanf("\n"); printf("%d\n",sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)); } } return 0; } 以上。 感谢 Mato,lyd 等神牛在这方面对我直接和/或间接的指导。


相关文章:
树状数组维护区间和的模型及其拓广的简单总结
树状数组维护区间和的模型及其拓广的简单总结_学科竞赛_高中教育_教育专区。树状数组维护区间和的模型及其拓广的简单总结 by wyl8899 树状数组的基本知识已经被讲到烂...
树状数组求区间和的一些常见模型
树状数组区间和的一些常见模型_IT/计算机_专业资料。实用树状数组区间和的一些常见模型树状数组在区间求和问题上有大用, 其三种复杂度都比线段树要低很多……有...
利用树状数组解决几类问题
树状数组作为一种实现简单、应用较广的高级数据结构,...题目中有两个元素:区间和颜色。如果直 接使用线段树...创意简历模板汇集 推理型题分析与总结文档贡献者 63...
树状数组
平常我们会遇到一些对数组进行维护查询的操作,比较常见的如,修改某 点的值、求某个区间的和,而这两种恰恰是树状数组的强项!当然,数据规模不 大的时候, 对于修改...
树状数组详解
使得修改和 求和复杂度均为 O(lgn),大大提高了...树状数组能快速求任意区间的和:A[i] + A[i+1]...的和 要求对每次查询,输出结果 5、总结 树状数组最...
树状数组简介
观察计算区间 [1,R],我们找到最大的 p,满足 2^...于 是我们利用树状数组维护 c 数组,这样时间复杂...id=2155 3、建模的一个例子: 建模的一个例子: ...
树状数组方法介绍
观察计算区间 [1,R],我们找到最大的 p,满足 2^...于 是我们利用树状数组维护 c 数组,这样时间复杂...id=2155 3、建模的一个例子: acm.hdu.edu.cn ...
树状数组及其应用
(X1,y1) (X2,y2) 四、总结 1、树状数组有两种模式的应用: 模式一:对数组 a[] 的某个元素作修改(O(logn)),查询某个区间内所有元素的和 (O(logn)) ...
一维与二维树状数组
昨天学了一下树状数组,随笔都写了一大半,结果一个不小心就把他给删了,哎。...修改,同时又要频繁的查询 数组内任一区间元素之和的时候,可以考虑使用树状数 ...
区间信息的维护与查询
区间信息的维护与查询_电脑基础知识_IT/计算机_专业资料。ACM资料区间...复杂度:预处理时间为 O(n),单 次时间为 O(1) 一、二叉索引树(树状数组)...
更多相关标签:
树状数组区间修改 | 树状数组求区间最大值 | 树状数组区间更新 | 树状数组 区间最值 | 树状数组求区间和 | 树状数组 区间最大值 | 树状数组区间最小值 | 二维树状数组区间修改 |