树状数组适用范围：给定区间，求最值，求和，区间单点修改。
与RMQ不同的是，RMQ一般只用作区间求最值。但在最值方面RMQ更加便捷。
树状数组
从图上可以看出要找到c[i]的父节点只要用i+x（x为i转化为二进制从右起第一个出现1的位置）就可以了
寻找x可以通过lowbit函数，即通过计算机补码的巧用，x=i&（-i）
int lowbit(int x)
{
return x&(-x);
}
而每一个父节点存储的数据都是下面所有子节点的全部信息。对子节点修改就必定会对其所有的父节点进行更新，父节点c[i]下标的查找如下：
void update(int i, int x)
{
while(i<=n)
{
c[i]+=x;
i+=lowbit(i);//更新父节点
}
}
对于查找1~i的和、最大值、最小值可以表示为：
int sum(int i)
{
int res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
典型例题（模版）：
HDU - 1166
对一个区域的数列进行查找、修改
#include<cstdio>
#include<cstring>
using namespace std;
int c[50005];
int n;
int lowbit(int x)
{
return x&(-x);
}
void update(int i, int x)
{
while(i<=n)
{
c[i]+=x;
i+=lowbit(i);//更新父节点
}
}
int sum(int i)
{
int res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
int main()
{
int T, cnt;
scanf("%d", &T);
for(cnt=1; cnt<=T; cnt++)
{
int i, temp;
char op[10];
memset(c,0,sizeof(c));
scanf("%d", &n);
for(i=1 ;i<=n; i++)
{
scanf("%d", &temp);
update(i, temp);
}
printf("Case %d:\n", cnt);
while(~scanf("%s", op))
{
int l, r, k;
if(!strcmp(op,"End")) break;
if(!strcmp(op,"Query"))
{
scanf("%d%d", &l, &r);
printf("%d\n", sum(r)-sum(l-1));
}
if(!strcmp(op,"Add"))
{
scanf("%d%d", &k, &temp);
update(k, temp);
}
if(!strcmp(op,"Sub"))
{
scanf("%d%d", &k, &temp);
update(k, -temp);
}
}
}
return 0;
}
例题：POJ - 3928
题目大意：在数列X中找到a、b、c
满足a<b<c和X[a]<X[b]<X[c]
思路：求取前缀和和后缀和的问题，update(X[i], 1);再getsum（）即可
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long int
const int maxn = 1e5+7;
const int max_num = 1e5;
int a[maxn];
ll c[maxn];
int pos_west[maxn], pos_east[maxn], neg_west[maxn], neg_east[maxn];
int lowbit(int x)
{
return x&(-x);
}
void update(int i, int p)
{
while(i<=max_num)
{
c[i]+=p;
i+=lowbit(i);
}
}
ll getsum(int i)
{
int res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
void init()
{
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
memset(pos_west,0,sizeof(pos_west));
memset(pos_east,0,sizeof(pos_east));
memset(neg_west,0,sizeof(neg_west));
memset(neg_east,0,sizeof(neg_east));
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int i, n;
ll sum=0;
scanf("%d", &n);
init();
for(i=1; i<=n; i++)
{
scanf("%d", &a[i]);
update(a[i],1);
pos_west[i]=getsum(a[i]-1);
pos_east[i]=getsum(max_num)-getsum(a[i]);
}
memset(c,0,sizeof(c));
for(i=n; i>0; i--)
{
update(a[i],1);
neg_west[i]=getsum(a[i]-1);
neg_east[i]=getsum(max_num)-getsum(a[i]);
}
for(i=1; i<=n; i++)
{
sum+=pos_west[i]*neg_east[i]+neg_west[i]*pos_east[i];
}
printf("%I64d\n", sum);
}
return 0;
}
注：此方法还可以用来求取逆序数！！！
例题：HDU - 1556
给定区间，每次在这个区间加1，求每个点一共加了多少次1
思路：前缀和思想，如图
前缀和
#include<cstdio>
#include<cstring>
using namespace std;
int c[100005];
int n;
int lowbit(int x)
{
return x&(-x);
}
void update(int i, int p)
{
while(i<=n)
{
c[i]+=p;
i+=lowbit(i);
}
}
int getsum(int i)
{
int res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
int main()
{
while(~scanf("%d", &n)&&n)
{
int a, b;
memset(c,0,sizeof(c));
for(int i=1; i<=n; i++)
{
scanf("%d%d", &a, &b);
update(a, 1);
update(b+1, -1);
}
for(int i=1; i<=n; i++)
{
if(i!=1) printf(" ");
printf("%d", getsum(i));
}
printf("\n");
}
return 0;
}
网友评论