线段树

2021-09-24

要解决的问题

数组任意区间内的元素修改,增加,求和,时间复杂度都要达到O(logN)水平, 方法说明如下

L...R上都加V

void add(L, R, V, arr) 

L...R上的值都更新成V

void update(L, R, V, arr)

L...R上求和并返回求和信息

int query(L, R, arr) 

预处理

线段树要求数组长度必须是2^N次方,如果不满足,则通过补0的方式来变成2^N次方。

将数组划分成一个个的区间,区间大小分别为: 1,2,4,8.... 2^N

例如:数组的长度为8,我们将数组下标从1开始编号到8,则每个下标构成的区间是一个满二叉树,如下图

        1~8
    /        \
  1~4        5~8
 /  \       /   \
1~2 3~4    5~6  7~8
/ \  / \   / \  / \
1 2  3 4   5 6  7  8

如果不满足2的n次方,要变成满二叉树,需要通过补0的方式,比如数组只有6个元素,编号为1~6,那么7位置和8位置补0。

如果N满足2的某次方,则仅需要2N个区间就可以装下所有区间,如果不满足2的某次方,则仅需要4N个区间就可以装下。

线段树这里的下标都用1开始,0位置弃而不用 就是为了在任意位置(假设位置为i)有:

左孩子对应的下标是2*i ,即:i<<1

右孩子对应的下标是2*i+1,即:(i<<1)|1

所以,假设原始数组长度为N,线段树需要将这个数组做如下预处理:

第一步,准备一个N+1长度的数组arr,arr的0位置弃而不用,其他位置依次存原始数组的值。

第二步,准备四个数组,数组长度均为:4*(N+1),每个数组的含义如下

sum数组用来模拟维护区间和

lazy数组为累加和懒惰标记

change数组为更新的值数组

update数组存放更新慵懒标记

线段树初始化

线段树在初始化阶段,会把每个区间的和先计算出来,放入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);
}

private void pushUp(int rt) {
  sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

pushUp方法很容易理解,即:每个区间的和等于它左右两个区间的和相加得到。前面提到,对于rt位置来说,左右孩子分别为rt << 1rt << 1 | 1。所以sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];

build方法用了递归,根据master公式可以计算其复杂度为O(logN)

区间内每个数都加一个值

即线段树的add方法,源码如下

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;
   }
   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);
   }
   pushUp(rt);
}

注:L...R为任务区间,即需要在L...R这个区间内的值,都加上一个C值。

如果任务的范围把此时数组某个划分区间l...r包住了,则这个l...r这个区间范围内的值都要加上C,

即代码中base case的第一个逻辑sum[rt] += C * (r - l + 1), 而lazy[rt] += C;表示加C这个任务hold在l...r区间内,不下发给子节点处理,这就是线段树的懒更新机制。

如果任务的范围无法把数组某个划分区间l...r包住,则l...r这个区间就要下发给左右子树进行处理。但是在下发之前,要进行pushDown操作,在pushDown操作中,add方法会触发到的逻辑是:

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] += lazy[rt] * ln;
    lazy[rt << 1 | 1] += lazy[rt];
    sum[rt << 1 | 1] += lazy[rt] * rn;
    lazy[rt] = 0;
   }
}

由于目前没有涉及update操作,所以现在只看pushDown方法的如下分支

   if (lazy[rt] != 0) {
    lazy[rt << 1] += lazy[rt];
    sum[rt << 1] += lazy[rt] * ln;
    lazy[rt << 1 | 1] += lazy[rt];
    sum[rt << 1 | 1] += lazy[rt] * rn;
    lazy[rt] = 0;
   }

这个操作表示,在l...r把任务下发到左右子树之前,先把l...r之前hold住的更新,即lazy[rt]中存的值,同步下发到左右子树进行更新,其中就包括两步:

第一步,左右子树都要加上之前父节点的lazy值,因为当时父节点在更新lazy的时候,是没有下发到左右子树的(懒更新),此时要下发了,就必须把之前所有的lazy信息更新到左右子树,对应就是代码中的如下两行

lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];

第二步,左右子树的sum值,也会随着父节点的lazy值更新过来而整体更新,对应代码中如下两行

sum[rt << 1 | 1] += lazy[rt] * rn;
sum[rt << 1] += lazy[rt] * ln;

pushDown的这两个步骤时间复杂度O(logN)。

此时,执行完pushDown操作后,就可以下发任务了,核心代码如下

   if (L <= mid) {
    add(L, R, C, l, mid, rt << 1);
   }
   if (R > mid) {
    add(L, R, C, mid + 1, r, rt << 1 | 1);
   }
   pushUp(rt);

使用的类似二分的方式,主要判断依据是任务区间到底在左右子树的哪个子树范围内。最后,执行pushUp方法,即把累加信息传递给父节点。

综上,线段树的add逻辑说明完毕。

区间内的值都更新为某个值

即线段树的update方法,update方法需要change数组和update数组配合。

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);
}

base case的逻辑和add方法类似,如果任务范围包住了区间范围,则在区间内直接做更新,update[rt] = true用于标识这个区间做了更新;change[rt] = C;用于记录这个区间的值更新成了什么;如果一个节点收到一个update方法,假设更新为C, 这个C存在change数组中,而且这个区间的所有lazy信息失效,这个区间的sum值直接变成数据个数 * C,所以有如下逻辑。

sum[rt] = C * (r - l + 1);
lazy[rt] = 0;

如果任务包不住区间范围,和add类似,也需要下发,下发过程可以查看pushDown逻辑的如下分支:

   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;
   }

下发过程中,左右子树的更新标志位都需要设置为true, 且左右子树区间需要更新的值均为父区间需要更新的值,即

update[rt << 1] = true;
update[rt << 1 | 1] = true;
change[rt << 1] = change[rt];
change[rt << 1 | 1] = change[rt];

由于区间需要更新,所以lazy失效,sum可以直接计算出来(数组区间元素个数*更新值)

任务下发后,和add方法一样,判断更新的区间在哪个子树范围,递归调用update执行更新操作即可,最后更新完毕后,需要把更新后的左右子树之和信息传给父节点的sum信息中。

综上,线段树的update方法说明完毕。

返回区间之和

add以及update方法类似,

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;
}

求和之前,如果任务范围没包住区间范围,要执行一次pushDown操作,才能把各个相关区间的信息最后整合出来。

线段树的适用场景

父节点如果可以通过左右简单加工得到,就可以用线段树

什么时候不能用线段树呢?

比如:要求某个区间出现次数最多的值(这个无法用线段树,因为出现次数最多的值可以既不是左边出现最多的值,也不是右边出现最多的值)

线段树源码

Code_0007_SegmentTree.java

相关题目

LeetCode_0307_RangeSumQuery

LeetCode_0303_RangeSumQueryImmutable

LeetCode_0699_FallingSquares

更多

算法和数据结构笔记

参考资料

程序员代码面试指南(第2版)

算法和数据结构体系班-左程云