在处理一些关于区间模型的问题时,常常会遇到处理前缀和(即从1到x的和)的问题。
这类问题常规解法有两种:
1、直接存储原数组,修改元素O(1),取前缀和O(n)。
2、直接存储前缀和,修改元素O(n),取前缀和O(1)。
但是如果当修改元素和取前缀和操作都比较大的时候,这两种方法就都不能用了。
怎么办呢?我们可以用另外一种解法:树状数组。
其修改元素和取前缀和的复杂度均为O(logn)。
如图所示,红色矩形表示的数组c[ ]就是树状数组。
这里,c[i] 表示 A[i-2^k+1] 到 A[i] 的和,而 k 是 i 在二进制表示下末尾0的个数。(我们可以利用位运算直接计算出2^k=i&-i)。
我们不难发现这个k就是这个节点在树中的高度,因而这个树的最大高度为logn。
1、对于修改操作,比如修改A[i]时,我们可以从c[i]往根节点(即往上)一路回溯,调整路上所遇到的c[ ]即可。
这个操作的复杂度在最坏情况下就是树的高度即O(logn)。
2、对于取前缀和操作,比如求sum(8),(即A[1]~A[8]的和),只需取 c[8] 的值就好了,因为c[8]保存的正是sum(A[1]~A[8])。
又比如求sum(7),就需要取 c[7]+c[6]+c[4] 的值,其中 c[7] = sum(A[7]),c[6] = sum(A[5]~A[6]),c[4] = sum(A[1]~A[4])。
显然,这些子树的数目是n在二进制表示下1的个数,或者说是n用2的幂方和表示时的多项式的项数。
因此,求和操作的复杂度是O(logn)。
树状数组主要有两个应用:
1、插点问线。
例题:士兵杀敌2->http://acm.nyist.net/JudgeOnline/problem.php?pid=116
问题特点:对单点更新,对区间询问,此处树状数组储存的是前缀和。
#include <stdio.h>
int n,m,a,b,c[1000003];
int lowbit(int x)
{
return x & -x;
}
void add(int loc,int val)
{
while(loc<=n)
{
c[loc] += val;
loc += lowbit(loc);
}
}
int sum(int loc)
{
int ans=0;
while(loc>0)
{
ans += c[loc];
loc -= lowbit(loc);
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
add(i,a);
}
char str[8];
while(m--)
{
scanf("%s%d%d",str,&a,&b);
if(str[0]=='A')
add(a,b);
else
printf("%d\n",sum(b)-sum(a-1));
}
return 0;
}
2、插线问点。
例题:士兵杀敌4->http://acm.nyist.net/JudgeOnline/problem.php?pid=123
问题特点:对区间更新,对单点询问,此处树状数组储存的是单点的值。
#include <stdio.h>
int n,m,a,b,x,c[1000010];
int lowbit(int x)
{
return x & -x;
}
void add(int loc,int val)
{
if(loc==0) //数据中有bug,特殊处理下,大牛请无视
loc = 1;
while(loc<=n)
{
c[loc] += val;
loc += lowbit(loc);
}
}
int sum(int loc)
{
int ans=0;
while(loc>0)
{
ans += c[loc];
loc -= lowbit(loc);
}
return ans;
}
int main()
{
scanf("%d%d",&m,&n);
char str[8];
while(m--)
{
scanf("%s",str);
if(str[0]=='A')
{
scanf("%d%d%d",&a,&b,&x);
add(a,x);
add(b+1,-x);
}
else
{
scanf("%d",&x);
printf("%d\n",sum(x));
}
}
return 0;
}
Ps:关于树状数组,最重要的一点就是,一定要从1开始,不能从0开始,因为lowbit(0)=0,会出现死循环。
分享到:
相关推荐
树状数组 树状数组 树状数组 树状数组树状数组 树状数组 树状数组 树状数组树状数组 树状数组 树状数组 树状数组
树状数组 树状数组.ppt
洛谷上关于树状数组的一些简单例题,可参考学习,适合初学者
用java实现的树状数组,可以作为一个简单的模版来进行应用,如果有不懂得地方,可以上网查找树状数组的原理
本文详细介绍了树状数组的原理,并用树状数组解校门外的树这个问题.
树状数组详解
树状数组 后缀数组 字典树 多串匹配算法及启示
树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现...
树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3....
其实学树状数组说白了就是看那张图,那张树状数组和一般数组的关系的,看懂了基本就没问题了,推荐下面这个教程:http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c...
里面包含了树状数组算法的描述和代码实现 里面包含了树状数组算法的描述和代码实现 里面包含了树状数组算法的描述和代码实现
你知道树状数组吗,这是本人自己打的课件,希望你能喜欢,有区间求值单点修改,单点修改区间查询,区间修改区间查询,二维树状数组......
含义其实就是用一个数组,构成树形结构来维护原数组的前缀和。 显然,对于树状数组C,C[I]对应“管辖”多少个元素,与它对应二进制数最右端第一个1的位置有关。这样,就能够达到询问一个区间的值,或者改变值的时间...
数据结构基础之树状数组,有关其实现代码,及树状数组的建立和点的更新。
图文并茂的描述了树状数组的使用~~让大家详细了解梳妆数组的使用
这是关于ACM 相关的 树状数组 算法资料。
它是ACM中关于二维树状数组方面的资料。。
树状数组要开long double(运算过程会爆long long)
该PPT详细的写了树状数组的(二叉索引树)区间和查询以及应用