前言

线段树是用来维护一段区间某种操作的树形数据结构，由于设计到区间，成员节点中l,r表示区间[l,r]。对于线段树的构造实际上是利用了二分的思想，从而使操作降到log级。

数据结构

struct Node {
	int l,r;
	int sum;
};
Node LTree[maxn << 2];

表示每个节点维护[l,r]区间的operator(这里的操作是区间和)，由于二分每个节点都有左右孩子，规模大小差不多是三倍N大，这里直接开4倍N。（这其实也可以动态分配内存，但是静态的简洁好写，减少BUG率）

建树

void Build (int l, int r, int idx) { //建立
	LTree[idx].l = l;
	LTree[idx].r = r;

	if (l == r) { //到达叶子节点
		LTree[idx].sum = val[l];
		return ;
	}
	int mid = l + ((r - l) >> 1);
	Build(l, mid, idx << 1);  //递归建立左子树
	Build(mid + 1, r, idx << 1 | 1); //递归建立右子树
	LTree[idx].sum = LTree[idx << 1].sum + LTree[idx << 1 | 1].sum; //左右孩子值更新完毕后把和传上来(PushUp)
}

后序遍历所有二分的区间，最后有个PushUp操作，其实就是把子区间的结果向上更新。

更新

void Update (int k, int num, int idx) { //更新
// LTree[idx].sum += num;
	if (LTree[idx].l == k && LTree[idx].r == k) { //更新到了叶子节点
		LTree[idx].sum += num;
		return ;
	}else if ( k <= (LTree[idx].l + ((LTree[idx].r - LTree[idx].l) >> 1)) ) { //k位置含于左区间
		Update(k, num, idx << 1);
	}else {  //k位置含于右区间
		Update(k, num, idx << 1 | 1);
	}
	LTree[idx].sum = LTree[idx << 1].sum + LTree[idx << 1 | 1].sum;
}

更新这里可以先序更新也可以后序更新区间操作。

  • 先序更新含义：
    我要在单点更新数字，先把包含该点的区间更新完毕后再找那个还包含该点的子区间更新。
  • 后序更新含义：
    我要在单点更新数字，先把包含该点的子区间更新完毕后，再更加子区间的所有情况向上更新母区间。

查询

int Query (int l, int r, int idx) { //查询
  if (l <= LTree[idx].l && r >= LTree[idx].r) { //查询的区间包含当前节点区间，这个节点的和全要
		return LTree[idx].sum;
	}else {
		int mid = LTree[idx].l + ((LTree[idx].r - LTree[idx].l) >> 1);
		if (r <= mid) { //完全在左区间中
			return Query(l, r, idx << 1);
		}else if (l > mid) { //完全在右区间中
			return Query(l, r, idx << 1 | 1);
		}else { //左右区间各占一部分
			return Query(l, mid, idx << 1) + Query(mid + 1, r, idx << 1 | 1);
		}
	}
}

这里很容易写错的地方是查询的是[l,r]包含的子区间而不是哪些子区间包含[l,r]。比如当我发现r<=mid后很容易就写成Query(l, mid, idx << 1)。而正确的就类似于把要查询的区间分成m个子区间，分别从这些子区间得到贡献反馈过来。所以递归的出口就是：当发现节点的区间被[l,r]完全包含时我就把这个值取出来，即完成了这一小部分。

HDU1166–AC代码

#include <iostream>
#include <string>
using namespace std;
typedef long long LL;
const int maxn = (int)5e4+5;

struct Node {
	int l,r;
	int sum;
};

int val[maxn],n;
Node LTree[maxn << 2];

void Build (int l, int r, int idx) { //建立
	LTree[idx].l = l;
	LTree[idx].r = r;

	if (l == r) { //到达叶子节点
		LTree[idx].sum = val[l];
		return ;
	}
	int mid = l + ((r - l) >> 1);
	Build(l, mid, idx << 1);  //递归建立左子树
	Build(mid + 1, r, idx << 1 | 1); //递归建立右子树
	LTree[idx].sum = LTree[idx << 1].sum + LTree[idx << 1 | 1].sum; //左右孩子值更新完毕后把和传上来(PushUp)
}

void Update (int k, int num, int idx) { //更新
// LTree[idx].sum += num;
	if (LTree[idx].l == k && LTree[idx].r == k) { //更新到了叶子节点
		LTree[idx].sum += num;
		return ;
	}else if ( k <= (LTree[idx].l + ((LTree[idx].r - LTree[idx].l) >> 1)) ) { //k位置含于左区间
		Update(k, num, idx << 1);
	}else {  //k位置含于右区间
		Update(k, num, idx << 1 | 1);
	}
	LTree[idx].sum = LTree[idx << 1].sum + LTree[idx << 1 | 1].sum;
}

int Query (int l, int r, int idx) { //查询
  if (l <= LTree[idx].l && r >= LTree[idx].r) { //查询的区间包含当前节点区间，这个节点的和全要
		return LTree[idx].sum;
	}else {
		int mid = LTree[idx].l + ((LTree[idx].r - LTree[idx].l) >> 1);
		if (r <= mid) { //完全在左区间中
			return Query(l, r, idx << 1);
		}else if (l > mid) { //完全在右区间中
			return Query(l, r, idx << 1 | 1);
		}else { //左右区间各占一部分
			return Query(l, mid, idx << 1) + Query(mid + 1, r, idx << 1 | 1);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;
	cin >> T;
	for (int k = 1; k <= T; k++) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> val[i];
		}
		Build(1, n, 1); //建立线段树
		string command;
		int i,j;
		cout << "Case " << k << ":\n";
		while (cin >> command && command.at(0) != 'E') {
			cin >> i >> j;
			switch (command.at(0)) {
			case 'A':
				Update(i, j, 1);
				break;
			case 'S':
				Update(i, -j, 1);
				break;
			case 'Q':
				cout << Query(i, j, 1) << '\n';
				break;
			default:
				break;
			}
		}
	}
	return 0;
}

总结

相比树状数组，线段树更容易理解，不过代码也比较难写，但是处理的问题范围比较大，但是常数也比较大。