本文将以单点更新、区间求和开启线段树的新世界。
—————————————————持续更新~———————————————————

另外文末会有链接传送，专门比较线段树和树状数组。

感谢优秀博客（讲述已十分详尽，这里只稍作总结）：
线段树从零开始
线段树详解

• 线段树是一种二叉搜索树，维护下标为1,2,..,n的n个按顺序排列的数的信息，这些数组合起来就是[1:n]的一个区间。
• 根结点表示的就是区间[1,n]，然后折半进行分解，直到不能分解，每个区间代表一个结点，每个结点存放各自的信息（如对于区间求和，每个结点存放着各区间的和）。
• 线段树同时是一棵平衡二叉树，所以可以用数组模拟树形结构，对于每一个非叶子结点[a,b],其左儿子表示的区间[a, (a+b)/2]，右儿子表示的区间是[(a+b)/2+1, b]。
• 这样一个树形结构查询、修改的时间复杂度都是O(n log n)

线段树实现单点更新、区间求和

1. 线段树构建

• a[]存放原数据，为便于使用，首位的值置于0； sum[]构建线段树，数组长度可给到 4n
• 从根结点开始递归，将[1, n]的区间两两分解，每一个非叶子结点表示的区间和，自然是左、右儿子的区间和相加；
• 树的最深层，也就是叶子结点存放原数据a[]
  • BuildUp()构建线段树
  • PushUp()更新每个结点

const int maxn = 100007;
int n = 10, a[11] = {0, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2};
int sum[maxn<<2];

void PushUp(int rt){
	sum[rt] = sum[rt<<1] + sum[rt<<1|1]; 
}
void BuildUp(int l, int r, int rt){//初始l=1, r=n, rt=1;
	if(l == r){//递归出口
		sum[rt] = a[l];
		return;
	}
	int m = (l+r) >> 1;//折半
	BuildUp(l, m, rt<<1);//从左儿子开始递归
	BuildUp(m+1, r, rt<<1|1);//从右儿子开始递归
	PushUp(rt);//分而治之
}

2. 线段树更新

• 初始化完毕，如果要对某个值进行更新（如实现 a[index]+=temp）；
• 自然也要从根结点开始，只扫描index包含的区间结点即可；
• 对于某一非叶子结点，要么从左儿子出发继续扫描，要么从右儿子出发继续扫描

void Update(int index, int temp, int l, int r, int rt){//实现a[index] += temp
	if(l == r){//最深层，存放a[]的位置
		sum[rt] += temp;
		return;
	}
	int m = (l+r) >> 1;
	if(index <= m)//index在左儿子的区间中
		Update(index, temp, l, m, rt<<1);
	else//反之，在右儿子区间中
		Update(index, temp, m+1, r, rt<<1|1);
	PushUp(rt);//扫描到的区间都要更新
}

1. 线段树求区间和
   求区间[l, r]的和，同样从根结点出发，扫描的过程就不是if…else了，因为所要查询的区间[l, r]可能既包含于左儿子的区间，又包含于右儿子所在的区间。

int Query(int L, int R, int l, int r, int rt){//求sum[l,r]
	if(l>=L && r<=R){
		return sum[rt];
	}
	int m = (l+r) >> 1;
	int ans = 0;
	if(m >= L)
		ans += Query(L, R, l, m, rt<<1);
	if(m < R)
		ans += Query(L, R, m+1, r, rt<<1|1);
	return ans;
}

线段树实现区间更新、区间求和

前面的都还好理解，下面需要用到的懒标记，是让我头疼了许多天都没解决的问题。
区间更新时使用懒标记

1. 如果按照单点更新的做法，要扫描到最深层，对区间[L,R]的每个点更新；
   其实当某结点所扫描的区间[l,r]包含在[L,R]内，就不用向下扫描了，直接对这个区间进行更新。

   if(L<=l && r<=R){//扫描的区间包含在[L,R]中，懒标记，不再向下扫描
   	lazy[rt] += temp;
   	sum[rt] += temp*(r-l+1);
   	return;
   }

然而，这样在更新时虽然可以减少递归的深度，很容易想到查询时会出现问题（下面的结点sum[]没有更新）。
2. 懒标记的引入，lazy[]标记各结点，初始为0，表示未被标记过。

• 懒标记存在的意义：本结点的统计信息已经根据标记更新过了，但是本结点的子结点仍需要进行更新。
• 所以无论是更新还是区间求和，都要PushDown()判断一下lazy[rt]，如果被标记过，需要更新左右子树

懒标记引入后需要增加的代码
——————————————————————————————————

int lazy[maxn<<2]; 
void PushDown(int rt, int ln, int rn){//更新子结点，ln rn分别为左子树 右子树区间长度
	if(lazy[rt]){
		lazy[rt<<1] += lazy[rt];
		lazy[rt<<1|1] += lazy[rt];
		sum[rt<<1] += lazy[rt]*ln;
		sum[rt<<1|1] += lazy[rt]*rn;
		lazy[rt] = 0;
	}
}
void Update(int L, int R, int temp, int l, int r, int rt){//实现 a[L,R] += temp;
	if(L<=l && r<=R){//扫描的区间包含在[L,R]中，懒标记，不再向下扫描
		lazy[rt] += temp;
		sum[rt] += temp*(r-l+1);
		return;
	}
	int m = (l+r) >> 1;
	PushDown(rt, m-l+1, r-m);//判断一下是否标记过
	if(L <= m)
		Update(L, R, temp, l, m, rt<<1);
	if(R > m)
		Update(L, R, temp, m+1, r, rt<<1|1);
	PushUp(rt);
}
int Query(int L, int R, int l, int r, int rt){
	if(l>=L && r<=R){
		return sum[rt];
	}
	int m = (l+r) >> 1;
	PushDown(rt, m-l+1, r-m);//判断一下是否标记过
	int ans = 0;
	if(m >= L)
		ans += Query(L, R, l, m, rt<<1);
	if(m < R)
		ans += Query(L, R, m+1, r, rt<<1|1);
	return ans;
}