目录

前言

树状数组

   lowbit函数

   直观表述 

      代码

      运行结果

树状数组构建代码

树状数组的应用

   单点修改和（单点）区间查询

   结合差分数组区间修改 ,单点查询

        差分数组

Color the ball hdu 1556

   问题描述

   问题分析

   代码

线段树 洛谷p3372

   问题描述

   问题分析        

   代码

---

前言

        树状数组和并查集一样，也是一个高级数据结构，编码简单，在算法竞赛中有着极其强大的应用。

• 并查集主要解决的是集合的问题，而树状数组主要解决的则是有关区间的问题；
• 并查集最本质的优化就是可以迅速找到元素所属的集合，树状数组则是可以在动态的数组中快速查询区间和。

树状数组

        树状数组，顾名思义，就是一个长得“很像”树的数组，本质上还是一个数组，但这个数组并不是常规的索引数组

   lowbit函数

        这个函数的功能是找到x的二进制数的最后一个1,换成十进制就表示能整除x的最大2的次幂

#define lowbit(x) ((x)&-(x))

   直观表述 

   下面我们来编写一个程序，直观表示下树状数组对应于数组的表示的元素

      代码

#include<iostream>
using namespace std;
const int N = 100005;

#define lowbit(x) ((x)&-(x))

int tree[N];

int main() {
	int n;
	cout << "输入树状数组的元素个数：";
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a = lowbit(i);
		cout << "tree[" << i << "] = ";
		int k = i;
		while(a){
			if (a == 1) {
				cout << "a[" << k << "]";
			}
			else cout << "a[" << k << "] + ";
			k--;
			a--;
		}
		cout << endl;
	}
}

      运行结果

        那么我们根据这个结果试着构建一棵线段树:

树状数组构建代码

#define lowbit(x) ((x)&-(x))

int segment_tree[N + 1] = {0};  //注意tree【0】不使用

void update(int x, int d) {
	while (x <= N) {
		segment_tree[x] += d;  //更新其所属的根节点
		x += lowbit(x);
	}
}

int sum(int x) {
	int ans = 0;
	while (x > 0) {
		ans += segment_tree[x];
		x -= lowbit(x);
	}
	return ans;
}

树状数组的应用

        树状数组的操作都是直接作用在数组上的，树状数组只是辅助作用

   单点修改和（单点）区间查询

    

        根据这个树状数组，假设我们要更新a[2],那么相应的就需要更新tree[2],tree[4],tree[8]

会发现:

• 2+lowbit(2)=4
• 4+lowbit(4)=8

那么我们就可以得出单点修改的代码：

void update(int x, int d) {
	while (x <= N) {
		segment_tree[x] += d;  
		x += lowbit(x);
	}
}

        树状数组区间查询是利用前缀和实现的，如果要算sum(7)，那么根据树状数组sum(7)=tree[7] + tree[6] + tree[4];会发现

• 7-lowbit(7)=6
• 6-lowbit(6)=4
• 4-lowbit(4)=0

那么我们就可以得到前缀和的算法：

int sum(int x) {
	int ans = 0;
	while (x > 0) {
		ans += segment_tree[x];
		x -= lowbit(x);
	}
	return ans;
}

        根据前缀和我们就可以计算任意区间【L,R】的区间和：sum(L) - sum(R-1) ，实现单点查询m：sum(m) - sum(m-1)

   结合差分数组区间修改 ,单点查询

        差分数组

        会发现使用树状数组时如果要进行区间修改是一件非常耗时的事情，应为树状数组的单点修改不仅仅要修改单个点，还要修改与该点相关的所有父节点，但差分数组可以快速实现区间修改，如果不是在线操作，那么将不需要将区间中所有元素修改个遍，所以将树状数组和差分数组结合可以极大提高在动态数组中区间修改的效率。

        树状数组结合差分数组时，我们将a[]数组当成差分数组，tree[]数组仍然是辅助，那么在进行单点查询的时候只需要调用sum（i）函数即可知道i节点的修改信息。 这里我们借助一道例题理解。

Color the ball hdu 1556

hdu 1556

   问题描述

        有几个气球排成一排，每次选择一个区间对这个区间内的气球涂色，经过几次涂色后问这些气球被涂色的次数。

   问题分析

        问题分析之前先介绍下先介绍下算法编程中的两种情况“离线”情况，“强制在线”情况

• 离线：是非交互的，一次读取很多信息，然后在对这些信息整合
• 强制在线：是交互的，要求一问一答        

         很明显，本题是一个离线情况，有多次操作，但只在最后查询，如果是离线操作那么就可以使用差分数组，这是一个常见的离线型数据结构（这个没必要特别记忆，练多了也就没有离线和在线之分了），因为差分数组可以记录修改信息，然后根据前缀和操作处理这些信息。

        所以本题可以定义一个差分数组，先记录被涂色信息，然后在最后应用前缀和算法计算涂色信息。但本题其实可以利用树状数组优化，前面说过了，树状数组最大的优势就是可以迅速得到前缀和，

        细心的朋友可能注意到，树状数组的修改操作不仅仅需要修改一头一尾，还要修改与头尾有关的根结点，但是如果只用差分数组的话，修改操作只需要修改区间的一头一尾即可，确实这样来看修改操作好像并没有优化，反而更加复杂，但这些都是值得的，因为如果是差分数组求前缀和是需要一个一个加的，但树状数组由于前面的准备操作，使得求前缀和操作不需要一项一项加，而且修改操作是一劳永逸的，因为在进行前缀和操作时，会发现会不止一次用到修改操作带来的数据，所以一切都是值得的，而且树状数组+差分需要的内存和只用差分所需内存一样多。

        所以我们可以将原数组a[](这个数组没必要在程序中定义，事实上树状数组的叶子节点就是a[]数组，也可以发现其实并不是a[]数组中每个元素在树状数组中都有对应，虽然树状数组和a[]数组开的内存一样，但树状数组更多的时根节点，代表根节点下所有叶子节点的和) 当成一个差分数组，然后结合树状数组高效解决这个问题，要知道修改信息只需要求前缀和即可。

   代码

#include<iostream>
#include <cstring> 
using namespace std;
const int N = 100005;
#define lowbit(x) ((x)&-(x))

int segment_tree[N+1] = { 0 };

void update(int i, int d) {
	while (i <= N) {
		segment_tree[i] += d;
		i += lowbit(i);
	}
}

int sum(int x) {
	int ans = 0;
	while (x > 0) {
		ans += segment_tree[x];
		x -= lowbit(x);
	}
	return ans;
}

int main() {
	int n, l, r;
	while (cin >> n && n) {
		memset(segment_tree, 0, sizeof(segment_tree));
		for (int i = 1; i <= n; i++) {
			cin >> l >> r;
			//差分数组操作
			update(l, 1);
			update(r + 1, -1);
		}
		for (int i = 1; i <= n; i++) {
			//输出修改信息
			if (i != n) {
				cout << sum(i) << " ";
			}
			else {
				cout << sum(i) << endl;
			}
		}
	}
}

        有人肯定会问，你这也不是单点查询啊，如果这个sement_tree初始值不是0，你这不就炸了吗，好好好，满足你的要求，我们再看一道例题。

线段树 洛谷p3372

洛谷 p 3372

   问题描述

        问题很简单，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 k。
2. 求出某区间每一个数的和。

   问题分析        

        很容易想到，这题的暴力求解，但肯定会超时，可以使用线段树解决（之后发篇博客，先欠着），我们这里尝试用用树状数组+差分。但在此之前我们还需要做一些小学二年级的数学推倒，如果数组不是初始为0，那么只用一个差分数组是无法实现求前缀和的，因为一个树状数组只能算出每个元素的修改值，想到这里肯定有人反映过来了，我们求出变化量来加到原数组中不就行了吗，这个操作可以利用树状数组的update函数实现：

• 也就是使用两个树状数组，
• 一个用于求原数组中每个数的变化量，
• 然后在另一个树状数组中利用update函数将这些变化量加到原数组上，
• 然后再利用第二个树状数组的sum函数求前缀和

        不用数学推导也可以实现，这不失为一个方法，能想到说明你对树状数组有一定理解了，但这样操做会发现，编码特别麻烦，不信你可以试一试，这个操作不是全是修改，而是修改和查询操作有可能交替进行。所以还是推导一下好。

        我们已知差分就是前缀和的逆操作，那么我们就可以进行一下推导：

设原数组a[]的差分数组为d[]

那么前缀和:

sum(i) = a[1] + a[2] +......+a[i]

sum(i) = d[1] + ( d[1] + d[2] ) + ( d[1] + d[2] +d[3] )  + ... + ( d[1] + d[2] + ... +d[i] )

sum(i) = id[1] + (i-1)d[2] + ... + [i-(i-1)]d[i]

sum(i) = i ( d[1] + d[2] + ... +d[i] ) - ( 0d[1] + d[2] + 2d[3] + ... + (i-1)d[i] )

sum(i) =      ( k=1~i )

        那我们就得到了一个公式：

sum(i) =      ( k=1~i )

        那么我们就可以定义两个树状数组+差分数组一个表示 ，另一个表示 

        想要都得到区间[L,R]只需要sum(L)-sum(R-1)即可：

   代码

#include<iostream>
using namespace std;
#define ll long long
#define lowbit(x) ((x)&-(x))

const int N = 100005;

ll segment_tree1[N + 1] = { 0 };
ll segment_tree2[N + 1] = { 0 };

void update(int x, ll d, int v) {
	if (v == 1) {
		while (x <= N) {
			segment_tree1[x] += d;
			x += lowbit(x);
		}
	}
	else {
		while (x <= N) {
			segment_tree2[x] += d;
			x += lowbit(x);
		}
	}
}

ll sum(int x,int v) {
	ll ans = 0;
	if (v == 1) {
		while (x > 0) {
			ans += segment_tree1[x];
			x -= lowbit(x);
		}
	}
	else {
		while (x > 0) {
			ans += segment_tree2[x];
			x -= lowbit(x);
		}
	}
	return ans;
}

int main() {
	int n, m, c, R, L;
	ll e=0,old,v;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		old = e;
		cin >> e;
		update(i, e-old, 1);
		update(i, (i - 1) * (e - old), 2);
	}
	for (int i = 1; i <= m;i++) {
		cin >> c;
		if (c == 1) {
			cin >> L >> R >> v;
			update(L, v,1);
			update(R + 1, -v, 1);
			update(L, (L - 1) * v, 2);
			update(R + 1, -R * v, 2);
		}
		else {
			cin >> L >> R;
			cout << R * sum(R, 1) - sum(R, 2) - (L - 1) * sum(L - 1, 1) + sum(L - 1, 2) << endl;
		}
	}
	return 0;
}