[数据结构]树状数组的基本应用

一、树状数组简介
二、树状数组的基本应用

一、树状数组简介

这部分内容只是对树状数组的简单复习，如果您不熟悉树状数组，可以自行百度或参考其他关于树状数组的博客。

树状数组(Binary Index Tree，BIT)是一种使用数组来模拟"树"的数据结构。树状数组的核心是lowbit(x)。
我们在对较大范围的连续线性范围统计时，我们通常按2的整数次幂分为若干小块处理。
同样的，树状数组也将一个大区间分为若干小区间。若区间区间结尾为R，区间长度就是R二进制分解后的最小二的次幂，也就是lowbit(R)：
例如： 6=(2^2+2^1),所以结尾为6的区间长度为2,即lowbit(6)=(2^1)=2。
8=(2^3)，所以lowbit(8)=(2^3)=8。
我们已经知道lowbit(x)所表达的含义，下面给出计算公式：lowbit(x)=x&(-x);
关于该公式的推导已经超出了我们讨论的范围，因此这里不再证明。
特别要注意的是，我们在做题的时候是不能计算lowbit(0)的，即不能调用数组下标0。由于lowbit(0)=0，调用的话会陷入死循环。
为什么使用lowbit(x)？为了避免查询与修改两种操作出现过高的复杂度(以前缀和为例，其区间查询的复杂度很低,而单点修改的复杂度却很高)，树状数组得以在O(logn)的复杂度内完成单点修改以及区间查询。
下图为树状数组操作时的模型图：(图片摘自百度百科)
下图为查询a[7]的前缀和的具体过程：
由于7=(2^2+2^1+2^0)，因此区间[1,7]可以分解成[1,4]、[5,6]、[7,7]这三个区间，长度分别为4,2,1。
我们可以看出c数组中保存的就是数组a的区间[x-lowbit(x)+1,x]中所有数的和，即:

[c[x]=sum_{i=x-lowbit(x)+1}^x a[i] ]

因此我们可以把c数组看做一种树形结构。c数组有以下性质：

c[x]保存的是以它为根的子树中所有叶节点的和。
c[x]的子节点数量=lowbit(x)
除根结点，c[x]的父节点为c[x+lowbit(x)]

由于树的深度为logn，因此复杂度为O(logn)。

下面分别为lowbit函数，修改以及查询的模板：

//lowbit函数
int lowbit(int x){return x&(-x);}

//修改
void Update(int x,int k){
	while(x<=n){
		c[x]+=k;
		x+=lowbit(x);
	}
}

//查询
int query(int x){
	int res=0;
	while(x>0){
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}

二、树状数组的基本应用

1.维护序列的前缀和（区间查询、单点修改）

最基础的用法。线段树可以实现树状数组的所有功能，但是树状数组的代码简短，可实施性强。因此在不必要的情况下不使用线段树。

例1: P3374【模板】树状数组1

题目描述：已知一个数列，你需要进行下面两种操作：1.将某一个数加上x； 2.求出某区间每一个数的和
思路：模板题。
代码：

#include<bits/stdc++.h>
#define N 500100
using namespace std;
int n,m,f[N];
inline int lowbit(int x){return x&(-x);}
void Update(int x,int s){
	while(x<=n){f[x]+=s;x+=lowbit(x);}
}
int Add(int x){
	int ans=0;
	while(x>0){ans+=f[x];x-=lowbit(x);}
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,d;i<=n;i++){
		scanf("%d",&d);
		Update(i,d);
	}
	for(int i=1,a,x,y;i<=m;i++){
		scanf("%d%d%d",&a,&x,&y);
		if(a==1) Update(x,y);
		else printf("%d
",Add(y)-Add(x-1));
	}
	return 0;
}

2.单点查询、区间修改

我们发现，应用二与一所解决的问题颠倒了。这样的话怎么处理呢？
我们引用一种新的方法：差分
设原数组a={1,3,2,4,8,6,7}，则对应的差分数组b={1,2,-1,2,4,-2,1}
得到规律：

[sum_{i=1}^k b_i=a_k ]

[b_i=a_i-a_{i-1} ]

最后的问题在于如何在差分数组上表示区间修改。
如下图：
图片1.png
每次区间加一个值val，只会对差分数组的(b_x)、(b_{y+1})有影响。
所以我们只需要修改两个值即可：update(x,val); update(y+1,-val);

例3: P1908 逆序对

题目描述：求序列中逆序对的个数
思路：我们每次读取一个值，就把这个值对应树状数组的下标加1，之后询问小于这个值的和，此时是比这个值小的数的个数。如果这个序列严格递增，那么这个值a[i]前面应该有i-1个比它小的值。我们可以知道如果这个个数小于i，那么这些数一定在a[i]的后面。因此用i减去比这个值小的数的个数(query(a[i]))就是这个数的逆序对个数。
代码：

#include<bits/stdc++.h>
#define ll long long
#define N 500010
using namespace std;
ll n,t[N],a[N],p[N],b[N],q[N],ans;
inline ll lowbit(ll x){
	return x&(-x);
}
inline void modify(ll x,ll k){
	while(x<=n){
		t[x]+=k;
		x+=lowbit(x);
	}
}
inline ll query(ll x){
	ll res=0;
	while(x>0){
		res+=t[x];
		x-=lowbit(x);
	}
	return res;
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	int m=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++){
		int pos=lower_bound(b+1,b+m+1,a[i])-b;
		q[i]=pos;
	}//离散化处理
	for(int i=1;i<=n;i++){
		modify(q[i],1);//统计逆序对个数
		ans+=i-query(q[i]);
	}
	printf("%lld",ans);
	return 0;
}

例4: UVA10810 Ultra-QuickSort

题目描述：使一个序列有小到大排列的两个数最小交换次数
思路：只有(a_i>a_j)是才会交换，故转化为逆序对处理。
代码：

#include<bits/stdc++.h>
#define N 500010
using namespace std;
int a[N],tree[N],maxpos,n;
inline int lowbit(int x){return x&(-x);}
inline void modify(int x,int k){
	while(x<=maxpos){
		tree[x]+=k;
		x+=lowbit(x);
	}
}
inline int query(int x){
	int res=0;
	while(x>0){
		res+=tree[x];
		x-=lowbit(x);
	}
	return res;
}
int main()
{
	while(scanf("%d",&n)&&n){
		maxpos=0;
		memset(tree,0,sizeof(tree));
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			a[i]++;
			maxpos=max(maxpos,a[i]);
		}
		int ans=0;
		for(int i=n;i>=1;i--){
			ans+=query(a[i]-1);
			modify(a[i],1);
		}
		printf("%d
",ans);
	}
	return 0;
}

例5: P1774 最接近神的人_NOI导刊2010提高（02）

思路：~~一道双倍经验题。~~与例三完全一致。

3.统计，计数

这类应用实际上基于树状数组的前缀和维护，使用时往往根据题目要求确定。

题目概述：给定长度为n的序列，接下来m次询问，让你求出区间内不同贝壳的种类。
用树状数组维护贝壳的种类个数。
具体过程为：
离线处理答案，按照询问的右区间进行排序；建立变量last表示上一个区间的右端点，初值last=1，建立hash[ ]数组表示出现贝壳的位置；
扫描last+1到当前区间的右端点，若hash[a[j]]为空，则说明贝壳没有出现过，这时候该位置修改为1，如果hash[ ]非空，那么减掉上一次贝壳出现位置并更新到现在的位置(此时由于仅求出种类，所以位置越靠右越好)，同样更新贝壳种类；
最后只要树状数组查询sum(r)-sum(l-1)，结果就是区间的贝壳数，结束后更新last=r[i]+1。
Code：

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int n,m,ans[N],Hash[N],a[N],t[N];
struct node{
	int l,r,id;
	bool operator <(const node &other) const{
		return r<other.r;
	}
}p[N];
inline int lowbit(int x){return x&(-x);}
inline int query(int x){
	int res=0;
	while(x>0){
		res+=t[x];
		x-=lowbit(x);
	}
	return res;
}
inline void modify(int x,int val){
	while(x<=n){
		t[x]+=val;
		x+=lowbit(x);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&p[i].l,&p[i].r);
		p[i].id=i;
	}
	sort(p+1,p+1+m);
	int last=1;
	for(int i=1;i<=m;i++){
		for(int j=last;j<=p[i].r;j++){
			if(Hash[a[j]]) modify(Hash[a[j]],-1);
			modify(j,1);
			Hash[a[j]]=j;
		}
		ans[p[i].id]=query(p[i].r)-query(p[i].l-1);
		last=p[i].r+1;
	}
	for(int i=1;i<=m;i++) printf("%d
",ans[i]);
	return 0;
}