树状数组简介

树状数组维护信息的类型:

树状数组一般用来维护可差分的信息

比如:累加和、累加乘或者出题人出了某个可差分的信息

不可差分的信息:比如最大值、最小值

不可差分的信息一般不用树状数组来维护，而会选择线段树来维护，因为线段树维护的思考难度低

大多数情况下，线段树可以代替树状数组，两者的时间复杂度差不多，单次调用都是O(log N)

线段树的优势:用法全面、思考难度低、维护信息类型多(包括可差分信息、不可差分信息)

线段树的劣势:代码较多、空间使用较大、常数时间较差

树状数组的优势:代码少、使用空间少、常数时间优异

树状数组的劣势:维护信息的类型少、维护某些不可差分的信息时思考难度大并且不易实现

一维数组上实现:单点增加、范围查询的树状数组

洛谷测试链接

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 100001

int tree[5 * N];//树状数组 
int n;//原始数组的元素个数 
int m;//操作次数 
//暂时存放数值的变量 
int t;
int a;
int b;

int lowbit(int x);//取出x的最右侧的一对应的数 
void add(int i, int v);//在i位置增加v 
int sum(int r);//返回[1, r]区间的累加和 
int range(int l, int r);//返回[l, r]区间的累加和 

int main(int argc, char* argv[])
{
	sc("%d%d", &n, &m);//读入元素个数和操作个数 
	
	for (int i = 1; i <= n; i ++) {//构成一个树状数组 
		sc("%d", &t);
		add(i, t);//假设树状数组刚开始都是0，现在开始添加数 
	}
	
	for (int i = 1; i <= m; i ++) {
		sc("%d%d%d", &t, &a, &b);//读入三个数 
		
		if (t == 1) {//如果t是1，把对应的位置的数加b 
			add(a, b);
		}
		else {//t是2，打印[a, b]区间的累加和	 
			pr("%d\n", range(a, b));
		}
	}
	
	return 0;
}

int lowbit(int x)
{
	return x & -x;	
} 

void add(int i, int v)
{
	while(i <= n) {//下标不能够超过元素个数 
		tree[i] += v;
		i += lowbit(i);//每次加lowbit去下一个包含i位置的区间 
	}
}

int sum(int r)
{
	int ans = 0;
	
	while(r) {
		ans += tree[r];
		r -= lowbit(r);//每次减lowbit去下一个包含[1, r]的区间 
	}
	
	return ans;
}

int range(int l, int r)
{
	return sum(r) - sum(l - 1);//前缀和求区间问题 
}

一维数组上实现:区间增加、单点查询的树状数组

洛谷测试链接

利用差分数组的性质来实现区间增加和单点查询，本质还是树状数组的操作但维护的信息不一样

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 100001

//树状数组维护差分信息 
int tree[N * 5] = {0};
int n;//原始数组的元素个数 
int m;//操作的次数 
int pre;//前一个元素默认为0 
//暂时存放的树的变量 
int t; 
int a[3];

int lowbit(int x);//返回x最右边的1对应的十进制 
void add(int i, int v);//在树状数组i位置的值增加v 
int sum(int r);//返回[1, r]范围的累加和 

int main(int argc, char* argv[])
{
	sc("%d%d", &n, &m);//读取数组的元素个数和操作个数 
	
	//读入数组的值 
	for (int i = 1; i <= n; i ++) {
		sc("%d", &t);
		
		add(i, t - pre);//把差分数组放入树状数组，树状数组来维护差分信息 
		pre = t;//存储前面的元素值，不然无法得到差分数组 
	}
	
	for (int i = 1; i <= m; i ++) {
		sc("%d", &t);//读入操作的类型 
		
		if (t == 1) {//给区间中的所有树增加一个值 
			sc("%d%d%d", a, a + 1, a + 2);
			//差分的操作 
			add(a[0], a[2]);
			add(a[1] + 1, -a[2]);
		}
		else {//单点查询 
			sc("%d", &a[0]);
			pr("%d\n", sum(a[0]));//差分数组的性质 
		}
	}
	
	return 0;
}

int lowbit(int x)
{
	return x & -x;	
} 

void add(int i, int v)
{
	while(i <= n) {
		tree[i] += v;
		i += lowbit(i);
	}
}

int sum(int r)
{
	int ans = 0;
	
	while(r) {
		ans += tree[r];
		r -= lowbit(r);
	}
	
	return ans;
}