树状数组
树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值。
树状数组十分容易实现,代码量小,时间复杂度低,并且经过数学处理后也可以实现成段更新。线段树也可以做到和树状数组一样的效果,但是代码要复杂得多。不过要注意,一般情况下树状数组能解决的问题线段树都能解决,反之有些线段树能解决的问题树状数组却不行。
代码如下:
int lowbit(int x)
{
return x & (-x);
}
void modify(int x,int add)//一维
{
while(x<=MAXN)
{
a[x]+=add;
x+=lowbit(x);
}
}
int get_sum(int x)
{
int ret=0;
while(x!=0)
{
ret+=a[x];
x-=lowbit(x);
}
return ret;
}
void modify(int x,int y,int data)//二维
{
for(int i=x;i<MAXN;i+=lowbit(i))
for(int j=y;j<MAXN;j+=lowbit(j))
a[i][j]+=data;
}
int get_sum(int x,int y)
{
int res=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
res+=a[i][j];
return res;
}
例题
- poj 2299 Ultra-QuickSort
题意为给定一个序列,求该序列中的逆序数的对数。
树状数组求解的思路:开一个能大小为这些数的最大值的树状数组,并全部置0。从头到尾读入这些数,每读入一个数就更新树状数组,查看它前面比它小的已出现过的有多少个数sum,然后用当前位置减去该sum,就可以得到当前数导致的逆序对数了。把所有的加起来就是总的逆序对数。
题目中的数都是独一无二的,这些数最大值不超过999999999,但n最大只是500000。如果采用上面的思想,必然会导致空间的巨大浪费,而且由于内存的限制,我们也不可能开辟这么大的数组。因此可以采用离散化的方式,把原始的数映射为1-n一共n个数,这样就只需要500000个int类型的空间。
代码如下:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 500005;
struct Node
{
int val;
int pos;
};
Node node[N];
int c[N], reflect[N], n;
bool cmp(const Node& a, const Node& b)
{
return a.val < b.val;
}
int lowbit(int x)
{
return x & (-x);
}
void update(int x)
{
while (x <= n)
{
c[x] += 1;
x += lowbit(x);
}
}
int getsum(int x)
{
int sum = 0;
while (x > 0)
{
sum += c[x];
x -= lowbit(x);
}
return sum;
}
int main()
{
while (scanf("%d", &n) != EOF && n)
{
for (int i = 1; i <= n; ++i)
{
scanf("%d", &node[i].val);
node[i].pos = i;
}
sort(node + 1, node + n + 1, cmp); //排序
for (int i = 1; i <= n; ++i) reflect[node[i].pos] = i; //离散化
for (int i = 1; i <= n; ++i) c[i] = 0; //初始化树状数组
long long ans = 0;
for (int i = 1; i <= n; ++i)
{
update(reflect[i]);
ans += i - getsum(reflect[i]);
}
printf("%lld\n", ans);
}
return 0;
}
poj 3468 A Simple Problem with Integers
题意:给你一个数列,每次询问一个区间的和,或者每次将一个区间的所有元素都加上一个数.
树状数组也可以实现区间更新,不过相比要比线段树区间更新难理解一些,具体过程如下:
首先,看更新操作update(s,t,d)把区间A[s]...A[t]都增加d,我们引入一个数组delta[i],表示A[i]...A[n]的共同增量,n是数组的大小。那么update操作可以转化为:令delta[s] = delta[s]+d,表示将A[s]...A[n]同时增加d,但这样A[t+1]...A[n]就多加了d,所以再令delta[t+1] = delta[t+1]-d,表示将A[t+1]...A[n]同时减d。
然后来看查询操作query(s, t),求A[s]...A[t]的区间和,转化为求前缀和,设sum[i] = A[1]+...+A[i],则 A[s]+...+A[t] = sum[t] - sum[s-1], 那么前缀和sum[x]又如何求呢?它由两部分组成,一是数组的原始和,二是该区间内的累计增量和,把数组A的原始值保存在数组org中,并且delta[i]对sum[x]的贡献值为delta[i]*(x+1-i),那么sum[x] = org[1]+...+org[x] + delta[1]*x + delta[2]*(x-1) + delta[3]*(x-2)+...+delta[x]*1 = org[1]+...+org[x] + segma(delta[i]*(x+1-i)) = segma(org[i]) + (x+1)*segma(delta[i])-segma(delta[i]*i),1<=i<=x=segma(org[i]-delta[i]*i)+(x+1)*delta[i], i<=1<=x.
这里就可以转化为两个个数组,这其实就是三个数组org[i],delta[i]和delta[i]*i的前缀和,org[i]的前缀和保持不变,事先就可以求出来,delta[i]和delta[i]*i的前缀和是不断变化的,可以用两个树状数组来维护。
代码如下:
#include<cstdio>
#include<cstring>
using namespace std;
long long int n;
long long bit0[200000],bit1[200000];
long long sum(long long *b,int i)
{
long long s=0;
while(i>0)
{
s+=b[i];
i-= i &(-i);
}
return s;
}
void add(long long *b,long long int i,long long int v)
{
while(i<=n)
{
b[i]+=v;
i+=i&(-i);
}
}
int main()
{
long long int i,j,k,a,b,c,m;
long long res;
char ch[100];
while(scanf("%lld%lld",&n,&m)!=EOF)
{
memset(bit0,0,sizeof(bit0));
memset(bit1,0,sizeof(bit1));
for(i=1;i<=n;i++)
{
scanf("%lld",&a);
add(bit0,i,a);
}
for(k=0;k<m;k++)
{
scanf("%s",ch);
if(ch[0]=='C')
{
scanf("%lld%lld%lld",&a,&b,&c);
add(bit0,a,-c*(a-1));
add(bit1,a,c);
add(bit0,b+1,b*c);
add(bit1,b+1,-c);
}
else
{
res=0;
scanf("%lld%lld",&a,&b);
res+=sum(bit0,b)+sum(bit1,b)*b;
res-=sum(bit0,a-1)+sum(bit1,a-1)*(a-1);
printf("%lld\n",res);
}
}
}
return 0;
}