树状数组

什么是树状数组

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

1.这是二叉树的结构

2.这是树状数组的结构

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

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

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

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

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

树状数组的优点

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

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

树状数组讲解

前置知识—lowbit(x)运算

问题引入

显然，我们一开始会想到暴力的朴素做法，单点修改操作时间复杂度O(1)，区间求和，暴力遍历区间每一个数再相加时间复杂度O(n)，如果区间求和查询的次数为n次，那么中的时间复杂度为O(  n^2  ）

对于大数据的题来说肯定会TLE，此时如果用树状数组的话复杂度可以降到O(nlogn).

树状数组结构分析

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

上面是树状数组的结构图，t[x]保存以x为根的子数中叶子节点值的和,原数组为a[]

t[1]=a[1],     t[2]=t[1]+a[2],     t[3]=a[3] ........ 这样t[8]就是a[1]~a[8]的和了
那么原数组前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)]

关于修改操作都是 i+=lowbit[i]，查询操作的都是 i-lowbit[i]

单点修改，区间查询

所以我们在单点修改的同时，更新父节点就变得尤为简单，，例如我们对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;
}

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

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;

int n, m, a[N], op, x, y, k, s[N];
int lowbit(int x)
{
	return x&(-x);
} 
void add(int x, int k)  
{
	for (int i=x; i<=n; i+=lowbit(i)) s[i]+=k;
}
int ask(int x, int y)
{
	int res=0;
	for (int i=y; i>=1; i-=lowbit(i)) res+=s[i];
	for (int i=x-1; i>=1; i-=lowbit(i)) res-=s[i];
	
	return res;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++) 
	{
		scanf("%d", &a[i]);
		add(i, a[i]);
	}
	
	while (m--)
	{
		scanf("%d", &op);
		if (op==1)
		{
			scanf("%d%d", &x, &k);
			add(x, k);
		}
		else if (op==2)
		{
			scanf("%d%d", &x, &y);
			printf("%d\n", ask(x, y));
		}
	}
	return 0;
}

树状数组2

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;

int n, m, a[N], op, x, y, k, s[N];
int lowbit(int x)
{
	return x&(-x);
} 
void add(int x, int k)  
{
	for (int i=x; i<=n; i+=lowbit(i)) s[i]+=k;
}
int ask(int x)
{
	int res=0;
	for (int i=x; i>=1; i-=lowbit(i)) res+=s[i];
	
	return res;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++) 
	{
		scanf("%d", &a[i]);
		add(i, a[i]-a[i-1]);
	}
	
	while (m--)
	{
		scanf("%d", &op);
		if (op==1)
		{
			scanf("%d%d%d", &x, &y, &k);
			add(x, k);
			add(y+1, -k);
		}
		else if (op==2)
		{
			scanf("%d", &x);
			printf("%d\n", ask(x));
		}
	}
	return 0;
}