我想要区间地修改/查询一些东西， 怎么搞比较快？
概念
名字叫作线段树，其实叫做区间修改树
线段树的指标是这3个方法全部达到O(logN)水平
为了让下标从1开始，0位置弃而不用
- 一个范围对应一个信息
- 一个大范围往下二分
- 比如要求累加和， 那么最底层的每个格子的累加和就是自己，然后父节点的累加和可以求了，依次往上
- 不管数组的长度是不是2^n次方，我们都希望构建出来的二叉树是满二叉树
- 比如数组长度是6， 那么我就通过补0的方式让它变成满二叉树，7位置和8位置补0，并且永远不修改它，我知道我实际的空间
- 为什么一定要是满二叉树？ 因为我们希望一个范围二分为左右两部分，左右两部分节点数要相同，也就是不想让分的时候范围不对齐
- 那么对于任意的长度N， 我需要准备多大的空间才够用？
- 4N
- 最省空间的时候，也就是N = 2的某次方的时候，是满二叉树的底层节点正好把数组每个分开，底层节点数N， 那么上面的需要N-1个空间就够了，
- 最浪费空间的时候呢？
- 比如N = 5
- 最底层，我需要5这个格子，还得另外再补充3个格子
- 也就是最底层左边是N - 1个数， 右边多出一个数
- 把N - 1看成N, 所以整个底层我需要准备2N空间， 往上我要准备2N - 1空间， 所以总的来说准备4N的空间绝对够用
接下来我们就来看是怎么构建的
我们要怎么表达这棵树呢？当然不能用二叉树了，用数组
问题来了，怎么找到一个具体的范围对应的下标是什么？
任何时候我最大的范围一定对应1下标（因为0位置我已经弃而不用了）
然后，比如我自己的下标是i， 那么我左孩子的下标就是2i， 右孩子的下标就是2i + 1
初始化
- 那么我们第一步就是初始化，把数组arr和数组sum填好
build(1 ~ 4, 1) 表示把arr 1~4范围的数求累加和后填到sum数组1位置上，
build(int l, int r, int rt)
也就是表示l~r范围对应于sum数组哪个下标
这里用到了位运算，也解释了为什么我们0位置弃而不用，就是为了可以在下标换算的时候用位运算代替
（因为你要是用0位置的话，那左孩子就是2i + 1, 右孩子就是2i + 2， 右孩子没法用位运算代替）
因为要从底层往上填信息，那我们可以从顶层递归下去
那么现在最上层节点的左孩子信息有了，右孩子信息也有了，就可以算我自己的了
然后剩下的所有东西你都可以认为是0。
至此我们的累加和信息就填好了，那如果我想要更多信息，无非就是搞更多和sum数组一样的数组，看在用户修改的时候怎么填这个数组，下标对应关系还是跟sum数组一样的
懒增加
比如说在1~6范围上的所有值给我加个4，
把（1~6）这个任务范围扔给顶层（1~8）， 这个任务范围没有彻底把（1~8）包括了，所以我要把我的任务下发
这时左节点，看见任务范围（1， 6）彻底把左节点自己的范围包括了，意味左节点所有范围的数都要加个4，好，左节点不下发了， 我把这个信息存也就是值4到lazy数组里对应位置去。
而右节点看任务范围（1，6）没有把右节点自己的范围包括了，所以右节点要下发， 下发给右节点的左节点，任务范围把自己的范围（5， 6）全部包住了， 所以不再下发，把信息也就是4存到lazy数组里对应的位置里去
你会发现，即使用了懒增加机制，还是有很多节点要往下传，那么这个代价是多少呢？ 代价是logN
比如 一个任务a~b范围任务发下来之后，相当于在左树走一个路径（左边界），再右树走一个路径（有边界），沿途要懒住的信息全懒住了，
那什么时候会破坏这个懒增加机制呢？
比如
这个（1~256）范围之前懒住的信息是这个范围的所有数都要加个7，所以lazy数组中对应位置的值就是7，
要是现在上游再来了个任务给它呢？比如(1~100) + 3，
我把之前我懒住的信息下发给我的孩子，(孩子是不再下发的)
也就是把我的懒更新信息下发一层
lazy[ (1~128) 对应下标 ] = 7
lazy[ (129~256) 对应下标 ] = 7
然后我自己的lazy信息就可以清空了， lazy[ (1 ~ 256) 对应下标 ] = 0
然后把这个新来的任务（1~100）+ 3 发给我的左孩子， 继续去执行这个流程，
这样还是在卡两个边界下去嘛
如果没有懒加载，那么每来一个任务所有节点都收到，那么就是O(N)了
懒更新
boolean类型的数组update[ ]
int 类型的数组change[ ]
为什么要个布尔类型的数组，因为change数组中默认的值是0， 比如说，你的数组中的数本来就是0，然后它又更新成0，那你怎么知道更新没更新？就用这个boolean类型数组update[]标记为true
- 那么有了update方法之后呢？就变得更复杂了
- 首先任何一个范围，如果它上面攒了一些lazy，那么执行update方法，比如所有值改成c，那么这个update任务会取消之前的所有的lazy， 也就是清空lazy，
- 举个例子
- 忽然来了个更新任务， 1~9范围上所有的值给我变成6
- lazy直接取消，sum就变成有上面有几个数乘6
- 举个例子
为什么pushDown方法里先是update相关内容再lazy相关内容？
举个例子
第一次任务是add操作 + 3
现在， 收到一个update任务把1~8范围全包了(改为5)
lazy清空
update数组值——> true
change数组值——-> 5
所以第二次的update操作会取消第一次的add操作，
然后现在来了第三个任务（1~8）范围上的数全都add 7
第四个任务（1~8）范围上的数全都add 5
所以lazy现在变成12，那当我要去下发的时候，我当然是先让下面的小弟该改的先改完，然后再把lazy上的搞一搞呀，
因为更新操作的时间序列在第三个和第四个任务之前呀。
如果大范围上攒了一个懒更新，那么子范围上的攒的懒更新和懒增加就无效了，
为啥？ 因为子范围如果有懒更新或懒增加，这怎么攒的？一定是大范围发给你的，而大范围在发给子范围的时候，会把所以的懒更新发给子范围，然后再执行， 因此，大范围上懒更新的东西一定要比子范围上的要晚，
举例子：
比如数组上全部数都是0
第一个任务 (1,4) add 2,
任务没法把顶层节点全包 ， 往下发
汇总
接下来来个update任务，（5~8） 改成1
任务没法把顶层节点全包， 往下发
汇总
接下来第三个任务来了，是个update任务， （1~8）所有数改成2，
任务范围把顶层节点范围全包了，不下发， （注意图中的update= 2， 对应代码中其实是 update数组 = true change数组 = 2） 
那么如果以后再发生update任务， 顶层节点的lazy一定会清空，然后改sum， update变成最近的值对吧，但是保不齐中间还有一些add任务来对不对，比如现在第4个任务来了，是个add任务，（1~8）add 3
第5个任务来了，是个add任务，（1~8）add 5
如果第6个任务来了，是个add任务 (1~7) add 1
任务范围没有把顶层范围全包，要下发， 但是我顶层节点攒了相当多的任务啊，
(1~7) add 1这个任务下发之前，先下发之前攒的任务，然后再发它
先下发什么？ 先下发update
update的发完了，开始发lazy，该怎么发就怎么发，
改完之后，就可以把这个（1，7） add 1任务发下去了
- query任务也是一样嘛
总代码
public static class SegmentTree {
/** arr[]为原序列的信息从0开始，但在arr里是从1开始的
* sum[]模拟线段树维护区间和
* lazy[]为累加懒惰标记
* change[]为更新的值
* update[]为更新慵懒标记 */
private int MAXN;
private int[] arr;
private int[] sum;
private int[] lazy;
private int[] change;
private boolean[] update;
public SegmentTree(int[] origin) {
MAXN = origin.length + 1;
arr = new int[MAXN]; // arr[0] 不用 从1开始使用
for (int i = 1; i < MAXN; i++) {
arr[i] = origin[i - 1];
}
sum = new int[MAXN << 2]; // 用来支持脑补概念中，某一个范围的累加和信息
lazy = new int[MAXN << 2]; // 用来支持脑补概念中，某一个范围沒有往下传递的累加任务
change = new int[MAXN << 2]; // 用来支持脑补概念中，某一个范围更新任务，更新成了什么
update = new boolean[MAXN << 2]; // 用来支持脑补概念中，某一个范围有没有更新操作的任务
}
/**在初始化阶段，先把sum数组填好
* 在arr[l~r]范围上，去build，1~N，
* @param rt 这个范围在sum中的下标
*/
public void build(int l, int r, int rt) {
if (l == r) {
sum[rt] = arr[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushUp(rt);
}
/** L..R --> 任务范围，所有的值累加上C
* l..r --> 你现在遇到的范围，就是实际范围
* rt 去哪找l..r范围上的信息 */
public void add(int L, int R, int C, int l, int r, int rt) {
// 任务的范围彻底覆盖了当前实际的范围
if (L <= l && r <= R) {
sum[rt] += C * (r - l + 1);
lazy[rt] += C;
return;
}
// 任务并没有把l...r全包住
// 要把当前任务往下发
int mid = (l + r) >> 1;
// 下发之前所有攒的懒任 务
pushDown(rt, mid - l + 1, r - mid);
if (L <= mid) {
add(L, R, C, l, mid, rt << 1);
}
if (R > mid) {
add(L, R, C, mid + 1, r, rt << 1 | 1);
}
// 左右孩子做完任务后，我更新我的sum信息
pushUp(rt);
}
public void update(int L, int R, int C, int l, int r, int rt) {
if (L <= l && r <= R) {
update[rt] = true;
change[rt] = C;
sum[rt] = C * (r - l + 1);
lazy[rt] = 0;
return;
}
// 当前任务躲不掉，无法懒更新，要往下发
int mid = (l + r) >> 1;
pushDown(rt, mid - l + 1, r - mid);
if (L <= mid) {
update(L, R, C, l, mid, rt << 1);
}
if (R > mid) {
update(L, R, C, mid + 1, r, rt << 1 | 1);
}
pushUp(rt);
}
// 1~6 累加和是多少？ 1~8 rt
public long query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return sum[rt];
}
int mid = (l + r) >> 1;
pushDown(rt, mid - l + 1, r - mid);
long ans = 0;
if (L <= mid) {
ans += query(L, R, l, mid, rt << 1);
}
if (R > mid) {
ans += query(L, R, mid + 1, r, rt << 1 | 1);
}
return ans;
}
/**之前的，所有懒增加，和懒更新，从父范围，发给左右两个子范围
* @param rt
* @param ln 左子树结点个数
* @param rn 右子树结点个数
*/
private void pushDown(int rt, int ln, int rn) {
if (update[rt]) {
update[rt << 1] = true;
update[rt << 1 | 1] = true;
change[rt << 1] = change[rt];
change[rt << 1 | 1] = change[rt];
lazy[rt << 1] = 0;
lazy[rt << 1 | 1] = 0;
sum[rt << 1] = change[rt] * ln;
sum[rt << 1 | 1] = change[rt] * rn;
update[rt] = false;
}
if (lazy[rt] != 0) {
lazy[rt << 1] += lazy[rt];
sum[rt << 1] += ln * lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
sum[rt << 1 | 1] += rn * lazy[rt];
lazy[rt] = 0;
}
}
private void pushUp(int rt) {
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
}
若有收获，就点个赞吧
0 人点赞
