树状数组介绍

在学习一个算法之前一定要清楚它能干嘛，能解决什么样的问题，对你解题是否有帮助，然后才去学习它!

那么接下来看如下几个问题

什么是树状数组

顾名思义就是一个结构为树形结构的数组，于二叉树的结构类似但又不同，它是在二叉树的结构上删除了一些中间节点，来看两幅图就明白了.

1.这是二叉树的结构

2.这是树状数组的结构

不难发现，树状数组相比于二叉树删除了一些节点，但是为什么要删除呢？这就和树状数组的一些性质(lowbit)有关了，不懂没关系，继续往下看.

树状数组可以解决什么问题呢？

可以解决大部分区间上面的修改以及查询的问题，例如1.单点修改，单点查询，2.区间修改，单点查询，3.区间查询，区间修改，换言之，线段树能解决的问题，树状数组大部分也可以，但是并不一定都能解决，因为线段树的扩展性比树状数组要强.

树状数组和线段树的区别在哪？

有人会问了既然线段树的问题能够用树状数组解决而且线段树还比树状数组扩展性强，那为什么不直接用线段树呢？问的很好，树状数组的作用就是为了简化线段树，举个例子：一个问题可以用线段树解决写代码半个小时，但是用树状数组只需要10分钟，那么你会选择哪一个算法呢?没错，基于某些简单的问题，我们没必要用到功能性强但实现复杂的线段树(杀鸡焉用宰牛刀).

树状数组的优点

优点：修改和查询操作复杂度于线段树一样都是logN,但是常数比线段树小，并且实现比线段树简单

缺点：扩展性弱，线段树能解决的问题，树状数组不一定能解决.

树状数组讲解

前置知识—lowbit(x)运算

如何计算一个非负整数n在二进制下的最低为1及其后面的0构成的数？
例如：$44=(101100{)}_2$,最低为1和后面的0构成的数是$(100{)}_2=4$
所以$lowbit(44)=lowbit((101100{)}_2)=(100{)}_2=4$,那么lowbit运算时怎么实现的呢？

44的二进制=(101100)，我们对44的二进制数取反+1，也即~44+1,得到-44

-44的二进制=(010100)，然后我们把44和-44的二进制进行按位与运算，也即按位&得到,二进制000100，也就是十进制的4

所以lowbit(x) = x&(-x)

问题引入

显然，我们一开始会想到暴力的朴素做法，单点修改操作时间复杂度O(1)，区间求和，暴力遍历区间每一个数再相加时间复杂度O(n)，如果区间求和查询的次数为n次，那么中的时间复杂度为O($n^2$),对于大数据的题来说肯定会T，此时如果用树状数组的话复杂度可以讲到O(nlogn).

树状数组结构分析

接下来分析树状数组的原理

上面时树状数组的结构图，t[x]保存以x为根的子数中叶子节点值的和,原数组为a[]
那么原数组前4项的和t[4]=t[2]+t[3]+a[4]=t[1]+a[2]+t[3]+a[4]=a[1]+a[2]+a[3]+a[4],看似没有什么特点，别着急往下看

我们通过观察节点的二进制数，进一步发现，树状数组中节点x的父节点为x+lowbit(x),例如t[2]的父节点为t[4]=t[2+lowbit(2)]

单点修改，区间查询

所以我们在单点修改的同时，更新父节点就变得尤为简单，，例如我们对a[1]+k，那么祖先节点t[1],t[2],t[4],t[8]都需要+k更新(因为t[]表示前缀和)，此时我们就可以用lowbit操作实现.
代码

int add_dandian(int x,int k)
{
	for(int i=x;i<=n;i+=lowbit(i))
	t[i]+=k;
}

那么单点修改实现了，如何实现区间查询呢？
例如：我们需要查询前7项的区间和sum[7]

通过图中不难看出，sum[7]=t[7]+t[6]+t[4] ,我们进一步发现,6=7-lowbit(7),4=6-lowbit(6)，所以我们可以通过不断的-lowbit操作来实现求和
代码

int ask(x){
	int sum = 0;
	for(int i=x;i;i-=lowbit(i)){
		sum+=t[i];
	}
	return sum;
}

这只能求区间$[1,x]的区间和，那么如何求[L,R]的区间和呢？$，这时候利用前缀和相减的性质就可以了，$[L,R]=[1,R]-[1,L-1]$
代码

int search(int L,int R)
{
	int ans = 0;
	for(int i=L-1;i;i-=lowbit(i))
	ans-=c[i];
	for(int i=R;i;i-=lowbit(i))
	ans+=c[i];
	return 0;
}

区间修改，单点查询

对于这一类操作，我们需要构造出原数组的差分数组c，然后用树状数组维护c数组即可

对于区间修改的话，我们只需要对差分数组进行操作即可，例如对区间[L,R]+k,那么我们只需要更新差分数组add(L,k),add(R+1,-k)，这是差分数组的性质.
代码

int update(int pos,int k)//pos表示修改点的位置,K表示修改的值也即+K操作
{
	for(int i=pos;i<=n;i+=lowbit(i))
	c[i]+=k;
	return 0;
}
update(L,k);
update(R+1,-k);

对于单点查询操作，求出c数组的前缀和即可，因为a[x]=差分数组c[1]+c[2]+…+c[x]的前缀和，这是差分数组的性质之一.
代码

ll ask(int pos)//返回区间pos到1的总和
{
	ll ans=0;
	for(int i=pos;i;i-=lowbit(i)) ans+=c[i];
	return ans;
} 

区间修改，区间查询

这一类操作使用树状数组就显得及其复杂，这时候我们建议使用扩展性更强的线段树来解决，在此就不进行树状数组的讲解了.

树状数组题目练习

下面2到题都是模板题，不需要经行讲解，学会了上面的树状数组知识就可以AC

树状数组1
AC代码

#include<iostream>
#define lowbit(x) (x&(-x))
typedef long long ll; 
using namespace std;
int c[2000006];
int n,m;
ll ans;
int add_dandian(int x,int k)
{
	for(int i=x;i<=n;i+=lowbit(i))
	c[i]+=k;
}
int search(int begin,int end)
{
	for(int i=end;i;i-=lowbit(i))
	ans+=c[i];
	for(int i=begin-1;i;i-=lowbit(i))
	ans-=c[i];
	return 0;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int number;
		scanf("%d",&number);
		add_dandian(i,number);
	}
	for(int i=1;i<=m;i++)
	{
		int choice,x,y;
		scanf("%d %d %d",&choice,&x,&y);
		if(choice==1) add_dandian(x,y);
		else
		{
			ans=0;
			search(x,y);
			printf("%lld\n",ans);
		}
	}
	return 0;
}

树状数组2

#include<iostream>
#include<cstring>
#define lowbit(x) (x&(-x)) 
using namespace std;
typedef long long ll;
const int Maxn=1e6+5;
int a[500005];
int d[Maxn]={0};//d[i]的值，d[i]表示第i和i-1个数的差值
ll c[Maxn]; 
int n,m;
int update(int pos,int k)//pos表示修改点的位置,K表示修改的值也即+K操作
{
	for(int i=pos;i<=n;i+=lowbit(i))
	c[i]+=k;
	return 0;
}
ll ask_qujian(int pos)//返回区间pos到1的总和
{
	ll ans=0;
	for(int i=pos;i;i-=lowbit(i)) ans+=c[i];
	return ans;
} 
int main()
{
	memset(c,0,sizeof(c));
	scanf("%d %d",&n,&m);
	a[0]=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		d[i]=a[i]-a[i-1];
		update(i,d[i]);
	}
	for(int i=1;i<=m;i++)
	{
		int choice,x,y,k;
		scanf("%d",&choice);
		if(choice==1)
		{
			scanf("%d %d %d",&x,&y,&k);
			update(x,k);
			update(y+1,-k);
		}
		else
		{
			scanf("%d",&x);
			printf("%lld\n",ask_qujian(x));
		}
	}
	return 0;
}

树状数组求逆序对
分析:对于原序列，比当前位置数大的数先出现在序列中，就会构成逆序对,例如：5 3 2 1，5,3,2比1先出现且都比1大，那么此时就构成了3个逆序对数,那么我们可以对已经出现的数字进行标记，枚举序列中每一个位置的数，统计有多少比它大的数字已经出现，然后累加进答案即可,这就是一个单点修改+区间查询的操作，树状数组实现,不过需要注意的是这道题数字很大，需要离散化存储.

注意：这道题自定义排序参数cmp的实现，不能单纯的a.val<b.val,如果相等的话也要保证位置不变,不然贡献会增多，想想为什么？.
AC代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn = 5e5+10;
int t[Maxn]={0};//树状数组 
typedef struct node{
   int val,ind;
}Node;
Node stu[Maxn];
int Rank[Maxn];
typedef long long ll;
int n; 
int lowbit(int x){return x&(-x);}
/*单点修改*/
void add(int pos){
	for(int i=pos;i<=n;i+=lowbit(i)) t[i]+=1;
}
/*区间求和*/
int ask(int pos){
	int ans = 0; 
	for(int i=pos;i;i-=lowbit(i)) ans+=t[i];
	return ans;
} 
/*不能单纯的a.val<b.val,如果相等的话也要保证位置不变,不然贡献会增多*/
int cmp(Node a,Node b){
	if(a.val==b.val)
	return a.ind<b.ind;
	
	return a.val<b.val;
}
int main()
{
	ll ans = 0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>stu[i].val;
		stu[i].ind=i;
	}
	sort(stu+1,stu+n+1,cmp);
	/*离散化操作*/
	for(int i=1;i<=n;i++){
		Rank[stu[i].ind] = i;
	} 
	for(int i=1;i<=n;i++){
		int pos = Rank[i];

		ans+=ask(n)-ask(pos);//digit+1~n中有多少数字已经出现就贡献多少逆序对数，累加到答案 
			add(pos);//单点修改
	}
	cout<<ans;
	return 0;
}