如果把树状数组和ST表比作手术刀，那么线段树就是一把大砍刀 ——题记

作用

线段树主要用于解决区间的修改与查询类问题，会搭配位运算或dp配合使用。

结构

如果把线段树画出来，大概长这个样子

其中结点上方的数字就是这个结点的编号，结点内部表示这个结点所维护的区间。

很容易发现，一个结点要么没有子结点，要么有$2$个子结点，而且父结点覆盖的区间恰好为$2$个子结点覆盖区间不重不漏组合而成，而且以中点断开，左儿子是左半部分，右儿子是右半部分。

还有一点，若一个结点的编号为$p$，则它的左儿子编号为$2p$，右儿子编号为$2p+1$。

玩转线段树

问题引入：给定长度为$n$一个序列$A$，有$q$个操作，操作类型有两种，一种是将$a_l,a_{l+1},a_{l+2},...,a_r$的所有数加上$k$，一种是询问$a_l+a_{l+1}+a_{l+2}+...+a_r$。

数据范围：$n\le 10^5,q\le 10^5$

遇题不决打暴力

像这种$n$和$q$都比较大的问题，且与区间相关，那么我们就可以愉快的考虑线段树了

如果我们已经知道了$a_1$与$a_2$的值，那么$a_1+a_2$是十分好求的这不废话吗

回到图中，如果我们知道了$8$号和$9$号结点的值，那么$4$号结点的值是非常好求的。

同理可得，如果我们知道了一个结点两个子结点的值，那么这个结点的值可以在$O(1)$内求出，只需将两个子结点的值相加即可。

于是，我们就easy的搞懂了线段树的第一个操作push_up

void push_up (int p) {
	tree[p].val = tree[p * 2].val + tree[p * 2 + 1].val;
}

求值

假设我们要查询的区间为$[2,4]$，从结点$1$开始，首先我们先取区间中点$3$，然后看我们查找的数据范围，$2\le 3$，所以要查询的区间一定存在它左儿子的某些部分，于是来到左儿子$2$处，同样取个中点$2$，$2\le 2$，所以继续查询左儿子$4$，取个中点$1$，发现$2>1$，所以需要查询的区间不在左儿子了，再比较发现$4>1$，所以要查询的区间包含了右儿子，来到右儿子$9$，此时发现$9$结点所覆盖的区间被需要查询的区间完全覆盖，于是直接返回$val$。回到$4$，再回到$2$，发现$4>2$，于是再到右儿子$5$……以此类推，从$1$最后返回值就是查询区间的值了。

这就是线段树的query函数

int query (int p,int l,int r) { 
	if (tree[p].l >= l && tree[p].r <= r) {    //如果当前结点覆盖的区间被查询区间完全包含
		return tree[p].sum;                    //直接返回即可
	}
	int mid = (tree[p].l + tree[p].r) / 2;
//	push_down(p);                                    这个是什么先不用管
	int res = 0;                               //不要忘记赋值为0哦
	if (l <= mid) res += query(p * 2,l,r);     //左儿子
	if (r > mid) res += query(p * 2 + 1,l,r);  //右儿子
	return res;
}

修改

单点修改

我们先不考虑依次修改一个区间，如果我们只修改一个点的话，应该怎么做呢？
和$query$类似，根据要修改的点的下标$idx$一直找到这个结点，然后将这个结点的$val$修改，注意逐层返回的时候执行一次$push$_$up$就OK了。

void add (int p, int idx, int k) {
	int tl = tree[p].l, tr = tree[p].r;
	if (tl == tr) {
		tree[p].val += k;
		return;
	}
	int mid = (tl + tr) / 2;
	if (idx <= mid) add(p * 2, idx, k);
	else add(p * 2 + 1, idx, k);
	push_up(p);
}

区间修改

要搞定这个东西首先我们要明白一个概念，懒标记。

这玩意是什么东西呢，就是说，如果我发现当前结点覆盖的区间被修改区间完全包含时，我就不用再一个一个改了，我直接根据区间的长度把区间的$val$加上去，然后打个标记，如果下次需要访问儿子了，再把这个标记传给儿子。懒啊

如图，我们要将$[3,5]$这个区间内的数全部加上$k$，左边的操作平平无奇，同单点一样，右边可就有意思了，直接走到$3$号结点，发现$3$号结点覆盖的区间被$[3,5]$完全包含，然后我们就可以偷个懒，直接把这个结点的$val$加上$2k$（因为覆盖区间长度是$2$，把这个区间内的数全部加$k$和也就大了$2k$），然后把这个结点的$add$，设为$k$就行了，这样在执行$query$操作时访问到这个结点，返回的就是修改后的值了，即使它的子结点们并没有真实增加。真够懒的

但还有一个问题需要解决，如果我要查询$[3,4]$呢？那这样不就访问到没有增加的结点了吗？
不慌，懒标记是可以由父结点向子结点传递的。

懒标记下传

首先将两个子结点的懒标记$add$都加上父结点的$add$，这点肯定都明白，然后我们按照区间修改的方法如法炮制，将子结点的$val$加上覆盖区间的长度乘父结点的$add$，最后将父结点的懒标记$add$清零就完成了懒标记的下传。

void push_down (int p) {
	tree[p * 2].add += tree[p].add;
	tree[p * 2 + 1].add += tree[p].add;
	tree[p * 2].sum += tree[p].add * (tree[p * 2].r - tree[p * 2].l + 1);
	tree[p * 2 + 1].sum += tree[p].add * (tree[p * 2 + 1].r - tree[p * 2 + 1].l + 1);
	tree[p].add = 0;
}

搞懂了懒标记，我们在回头去看$query$函数，现在那行注释掉的代码作用也就自己出来了。

你学会了之后兴冲冲地拿着C++一通撸，结果发现输出的全是0？

建树

刚才说了半天操作，却没有把树建出来啊，那这个就很尴尬了。建树过程还是很简单的。如果当前分配区间的$l$和$r$相同，那么说明到了叶子，将$val$设为$a_l$，否则继续取中点，递归建立整棵线段树。

void build (int p,int l,int r) {
	tree[p].l = l;
	tree[p].r = r;
	if (l == r) {
		tree[p].sum = a[l];
		return;
	}
	int mid = (tree[p].l + tree[p].r) / 2;
	build(p * 2,l,mid);
	build(p * 2 + 1,mid + 1,r);
	push_up(p);
}

时间复杂度分析

建树的复杂度显然是$nlogn$的，根据代码可以很明显的看出，区间的查询与修改时间复杂度相同，但具体是多少呢？这个比较难估计。我们来思考一下，在第一次将函数分出两个之前，一直是一通下来，很好估计，分出两个以后呢？我们来看左儿子的区间，首先，查询区间的右端点是一定超过左儿子的右端点的（不然就不会分出两个了），我们只需要估计左端点即可，我们先将左儿子的区间等分为两部分，如果左端点在右边那一部分，那么还是只有一个函数在继续递归，如果左端点在左边部分的话，那么右边部分的区间是被查询区间完全包含的，可以在$O(1)$内求出，所以还是一个函数在递归。这样的话，总时间复杂度就为$2logn$，是非常优的一个时间复杂度了。