最近寒假，就来学习了一下线段树，其实挺简单的。

通过一个树状数组来维护线段树，在区间求和和单点更新只需要维护个sum的树状即可，sum[1]表示1为根的区间[1, n]的和

因为是树状数组，就不用记他的区间，用左孩子 rt/2 和右孩子 rt/2+1 。

这里不详细介绍，想仔细学的这里有

我的宏定义

#define lson l, m, rt << 1#define rson m+1, r, rt << 1 | 1#define MID (l+r) >> 1#define lc rt << 1#define rc rt << 1 | 1

其中lson和rson是用来传递参数方便的， rt << 1 | 1 等同于 rt / 2 + 1

首先，是

• 单点更新和区间求和的普通线段树
  #include 
         
          using namespace std;#define lson l, m, rt << 1#define rson m+1, r, rt << 1 | 1#define MID (l+r) >> 1#define lc rt << 1#define rc rt << 1 | 1const int maxn = 1e5 + 10;int sum[maxn << 2];void pushUp(int rt) {	sum[rt] = sum[lc] + sum[rc];}void update(int p, int key, int l, int r, int rt) {	if(l == r){ //当l == r 说明已经找到了，注意，这里不能用rt == p ，因为顺序是不同的		sum[rt] += key;		return;	}	int m = MID;	if(p <= m) update(p, key, lson); //如果p点在左边	else update(p, key, rson);	pushUp(rt); //维护子树根的和}void build(int l, int r, int rt) {	if(l == r) {		scanf("%d", &sum[rt]); //从树状数组内初始化，注意，顺序是不同的		return;	}	int m = MID;	build(lson); build(rson); //向左右拓展开	pushUp(rt); //维护子树根的和}int query(int L, int R, int l, int r, int rt) {	if(L <= l && r <= R) return sum[rt]; //找到符合条件的根，返回	int m = MID, ret = 0;	if(L <= m) ret += query(L, R, lson); //向区间[l, m]寻找	if(m < R) ret += query(L, R, rson); //向区间[m+1, r]寻找	return ret;}int main() {	int n, m, a, b, c;	scanf("%d", &n);	build(1, n, 1);	scanf("%d", &m);	for(int i = 0; i < m; ++i) {		scanf("%d%d%d", &c, &a, &b);		if(c == 1) update(a, b, 1, n, 1);		else printf("%d\n", query(a, b, 1, n, 1));	}	return 0;}
         

   例题:
• 成段更新（区间更新单点多点求和）

   在单点更新的基础上，引入另一个树状数组，我们称为懒惰标记，就是当一段更新时，我们只在对应的区间做个标记，并不让区间的所有元素更新，当询问时，在一层层地向下传递，所以我们引入个新的函数 pushdown()，就是将信息从父亲节点传递到子节点。具体的看lrj的白书或看上面链接大神的博文。

  代码如下： （）
  #include 
         
          using namespace std;#define lson l, m, rt << 1#define rson m+1, r, rt << 1 | 1#define MID ((l+r) >> 1)#define lc rt << 1#define rc rt << 1 | 1typedef long long ll;const int maxn = 200000 + 10;ll sum[maxn << 2], add[maxn << 2]; //add为懒惰标记int L, R, _add;void pushup(int rt) {	sum[rt] = sum[lc] + sum[rc];}void pushdown(int rt, int m) {	if(add[rt]) { //向子节点两边传递根节点的更新值		add[lc] += add[rt];		add[rc] += add[rt];		sum[lc] += add[rt] * (m - (m >> 1)); //想想，为什么是(m - (m >> 1)) 和 (m >> 1)		sum[rc] += add[rt] * (m >> 1);		add[rt] = 0; //当传递下去后，要清除标记	}}void build(int l, int r, int rt) {	add[rt] = 0; //可以顺便初始化 PS:在对同一数组建多次线段树有用	if(l == r) {		scanf("%lld", &sum[rt]);		return;	}	int m = MID;	build(lson); build(rson);	pushup(rt);}void update(int l, int r, int rt) {	if(L <= l && r <= R) {		add[rt] += _add; //更新区间的懒惰标记		sum[rt] += _add * (r-l+1); //将和要全部加上它所有子节点更新后的值		return;	}	pushdown(rt, r-l+1); //先向下传递 因为是从上到下传递，所以要放在递归前	int m = MID;	if(L <= m) update(lson); //左右拓展	if(m < R) update(rson);	pushup(rt);}ll query(int l, int r, int rt) {	if(L <= l && r <= R)		return sum[rt];	pushdown(rt, r-l+1); //将当前的标记全部传递下去，要不然得不到答案	int m = MID;	ll ret = 0;	if(L <= m) ret += query(lson);	if(m < R) ret += query(rson);	return ret;}int main() {	int n, q, t;	scanf("%d", &n);	build(1, n, 1);	scanf("%d", &q);	for(int i = 0; i < q; ++i) {		scanf("%d%d%d", &t, &L, &R);		if(t == 1) { scanf("%d", &_add); update(1, n, 1); }		else printf("%lld\n", query(1, n, 1));	}		return 0;}
         

  单点查询就直接将左区间等于右区间即可。