# 前言

为什么会用到线段树？可以在 log(n) 的情况下查询和更新区间。

若用现在有一个这样的问题：有一个数组 a ，下标从 0 到 n-1 ，现在给你 w 次修改， q 次查询，修改的话是修改数组中某一个元素的值；查询的话是查询数组中任意一个区间的和， w + q < 500000 。

这个问题很常见，首先分析下朴素做法的时间复杂度，修改是 O(1) 的时间复杂度，而查询的话是 O(n) 的复杂度，总体时间复杂度为 O(qn) ；可能你会想到前缀和来优化这个查询，我们也来分析下，查询的话是 O(1) 的复杂度，而修改的时候修改一个点，那么在之后的所有前缀和都要更新，所以修改的时间复杂度是 O(n) ，总体时间复杂度还是 O(qn) 。

可以发现，两种做法中，要么查询是 O(1) ，修改是 O(n) ；要么修改是 O(1) ，查询是 O(n) 。那么就有没有一种做法可以综合一下这两种朴素做法，然后整体时间复杂度可以降一个数量级呢？有的，对，就是线段树

# 线段树与懒加载

挑选 O(n) 个特殊区间，使得任意一个区间可以拆分为 O(log n) 个特殊区间（用最近公共祖先思考）
- O(n) <= 4n , 因为最后一层 n 个，倒数第二层 n / 2 个... 第一层 1 个
lazy 更新 / 延迟更新
lazy tag : 用一个数组维护每个区间需要更新的值
若这个值 = 0，表示不需要更新
若这个值！=0，表示之前更新操作再这个区间停住了，不继续递归子区间了。此时又来了一个更新，破坏了 lazy tag 的区间，那么这个区间就得继续递归更新了，直到在范围内停止递归，后面又来了一个更新...

若不用 lazy tag 则最坏情况下会更新每个节点，例如上述的 [1, 10]

不断地递归更新子区间， O(n)

# 模板

	public class Solution {
	/*

	*/
	int n;
	//lazy tag
	int[] lazyTag = new int[4 * n];
	int[] tree = new int[4 * n];

	// 更新 [L, R]
	public void update(int o, int l, int r, int L, int R, int add) {
	// 完全包含
	if (L <= l && r <= R) {
	// 维护... 不在继续递归更新了
	lazyTag[o] += add; // 懒加载
	return;
	}
	// 递归的更新左右区间
	// 需要继续递归，就需要将 lazyTag [o] 的内容传下去（给左右儿子）
	if (lazyTag[o] != 0) {
	lazyTag[o * 2] += lazyTag[o];
	lazyTag[o * 2 + 1] += lazyTag[o];
	lazyTag[o] = 0; // 自身清零
	}
	int m = (l + r) / 2;

	// 例如 : m = 5, [L, R] = [1, 7]
	// [1, 5], [6, 10]
	// [1, 5] 停止更新，[6, 10] 继续递归

	// 中间值 m >= L
	if (m >= L) {
	update(o * 2, l, m, L, R, add);
	}
	// 中间值 m + 1 <= R
	if (m < R) {
	update(o * 2 + 1, m + 1, r, L, R, add);
	}
	// 维护... 不在继续递归更新了
	}

	public int query(int o, int l, int r, int L, int R) {
	// 完全包含
	if (L <= l && r <= R) {
	return tree[o];
	}
	int m = (l + r) / 2;
	int ans = 0;
	// 递归的更新左右区间
	// 需要继续递归，就需要将 todo [o] 的内容传下去（给左右儿子）
	if (lazyTag[o] != 0) {
	lazyTag[o * 2] += lazyTag[o];
	lazyTag[o * 2 + 1] += lazyTag[o];
	lazyTag[o] = 0; // 自身清零
	}
	// 中间值 m >= L
	if (m >= L) {
	ans += query(o * 2, l, m, L, R);
	}
	// 中间值 m + 1 <= R
	if (m < R) {
	ans += query(o * 2 + 1, m + 1, r, L, R);
	}
	return ans;
	}

	}