Segment tree

主要作用

线段树是主要用来维护区间信息的数据结构
线段树可以在O(logN)的时间复杂度内实现单点修改、区间修改、区间查询(区间求和、求区间最大值、求区间最小值)等操作

基本结构

将数组a={10,11,12,13,14}转化为线段树:设线段树的根节点编号为1，用数组d来保存我们的线段树,$d_i$用来保存线段树上编号为i的节点的值，这里每个节点所维护的值就是这个节点所表示的区间总和。

$d_i$的左儿子节点就是$d_{2*i}$,$d_i$的右儿子节点就是$d_{2*i+1}$.如果$d_i$表示的是区间[s,t](即$d_i$=$a_s$+$a_{s+1}$+...+$a_t$)的话，那么$d_i$的左儿子节点表示的是区间[s,$\frac{s+t}{2}$],$d_i$的右儿子表示的区间为$\frac{s+t}{2}$+1到t的闭区间

建树

在实现时，我们考虑递归建树。设当前的根节点为$p$,如果根节点管辖的区间长度已经是1,则可以直接根据a数组上相应位置的值初始化该节点。否则我们将该区间从中点处分割为两个子区间，分别进入左右子节点递归建树，最后合并两个子节点的信息。

• c++

void build(int s, int t, int p) {
  // 对 [s,t] 区间建立线段树,当前根的编号为 p
  if (s == t) {
    d[p] = a[s];
    return;
  }
  int m = s + ((t - s) >> 1);
  // 移位运算符的优先级小于加减法，所以加上括号
  // 如果写成 (s + t) >> 1 可能会超出 int 范围
  build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
  // 递归对左右区间建树
  d[p] = d[p * 2] + d[(p * 2) + 1];
}

• python

def build(s, t, p):
    # 对 [s,t] 区间建立线段树,当前根的编号为 p
    if s == t:
        d[p] = a[s]
        return
    m = s + ((t - s) >> 1)
    # 移位运算符的优先级小于加减法，所以加上括号
    # 如果写成 (s + t) >> 1 可能会超出 int 范围
    build(s, m, p * 2)
    build(m + 1, t, p * 2 + 1)
    # 递归对左右区间建树
    d[p] = d[p * 2] + d[(p * 2) + 1]

• golang

package main

import "fmt"

// 假设数组 a 和线段树数组 d 已经定义
var a []int
var d []int

func build(s, t, p int) {
    // 对 [s,t] 区间建立线段树，当前根的编号为 p
    if s == t {
        d[p] = a[s]
        return
    }
    m := s + ((t - s) >> 1)
    // 递归对左右区间建树
    build(s, m, p*2)
    build(m+1, t, p*2+1)
    d[p] = d[p*2] + d[p*2+1]
}

func main() {
    // 示例
    a = []int{0, 1, 2, 3, 4, 5} // 下标从 1 开始
    d = make([]int, 4*len(a))
    build(1, len(a)-1, 1)
    fmt.Println(d)
}

• java

public class SegmentTree {
    static int[] a; // 原数组，下标从 1 开始
    static int[] d; // 线段树数组

    static void build(int s, int t, int p) {
        // 对 [s,t] 区间建立线段树，当前根的编号为 p
        if (s == t) {
            d[p] = a[s];
            return;
        }
        int m = s + ((t - s) >> 1);
        // 递归对左右区间建树
        build(s, m, p * 2);
        build(m + 1, t, p * 2 + 1);
        d[p] = d[p * 2] + d[p * 2 + 1];
    }

    public static void main(String[] args) {
        a = new int[]{0, 1, 2, 3, 4, 5}; // 下标从 1 开始
        d = new int[4 * a.length];
        build(1, a.length - 1, 1);
        for (int val : d) {
            if (val != 0) System.out.print(val + " ");
        }
    }
}

关于线段树的空间:如果采用堆式存储,$2p$是$p$的左儿子,$2p+1$是$p$的右儿子,若有n个叶子节点,则d数组的范围最大为$2^{\lceil log_n \rceil +1}$

容易知道线段树的深度是$\lceil log_n \rceil$的，则在堆式存储情况下叶子节点(包括无用的叶子节点)数量为$2^{\left\lceil\log{n}\right\rceil}$个，又由于其为一棵完全二叉树，则其总节点个$2^{\left\lceil\log{n}\right\rceil+1}$-1。当然如果你懒得计算的话可以直接把数组长度设为$4n$，因为 $\frac{2^{\left\lceil\log{n}\right\rceil+1}-1}{n}$的最大值在$n=2^{x}+1(x\in N_{+})$时取到，此时节点数为$2^{\left\lceil\log{n}\right\rceil+1}-1=2^{x+2}-1=4n-5$

而堆式存储存在无用的叶子节点，可以考虑使用内存池管理线段树节点，每当需要新建节点时从池中获取。自底向上考虑，必有每两个底层节点合并为一个上层节点，因此可以类似哈夫曼树地证明，如果有$n$个叶子节点，这样的线段树总共有$2n-1$个节点。其空间效率优于堆式存储，并且是可能的最优情况

这样的线段树可以自底向上维护

线段树的区间查询

区间查询，比如求区间[l,r]的总和(即$a_l$+$a_{l+1}$+…+$a_r$)、求区间最大值/最小值等操作

• cpp

int getsum(int l, int r, int s, int t, int p) {
  // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
  if (l <= s && t <= r)
    return d[p];  // 当前区间为询问区间的子集时直接返回当前区间的和
  int m = s + ((t - s) >> 1), sum = 0;
  if (l <= m) sum += getsum(l, r, s, m, p * 2);
  // 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  // 如果右儿子代表的区间 [m + 1, t] 与询问区间有交集, 则递归查询右儿子
  return sum;
}

• python

def getsum(l, r, s, t, p):
    # [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
    if l <= s and t <= r:
        return d[p]  # 当前区间为询问区间的子集时直接返回当前区间的和
    m = s + ((t - s) >> 1)
    sum = 0
    if l <= m:
        sum = sum + getsum(l, r, s, m, p * 2)
    # 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
    if r > m:
        sum = sum + getsum(l, r, m + 1, t, p * 2 + 1)
    # 如果右儿子代表的区间 [m + 1, t] 与询问区间有交集, 则递归查询右儿子
    return sum

• golang

// d 是全局数组，存储线段树节点的值
func getsum(l, r, s, t, p int, d []int) int {
    // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
    if l <= s && t <= r {
        return d[p] // 当前区间为询问区间的子集时直接返回
    }
    m := s + ((t - s) >> 1)
    sum := 0
    if l <= m {
        sum += getsum(l, r, s, m, p*2, d)
    }
    if r > m {
        sum += getsum(l, r, m+1, t, p*2+1, d)
    }
    return sum
}

• java

class SegmentTree {
    int[] d; // 存储线段树节点的数组

    public SegmentTree(int size) {
        d = new int[size * 4]; // 足够容纳线段树节点
    }

    public int getsum(int l, int r, int s, int t, int p) {
        // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
        if (l <= s && t <= r) {
            return d[p]; // 当前区间为询问区间的子集时直接返回
        }
        int m = s + ((t - s) >> 1);
        int sum = 0;
        if (l <= m) {
            sum += getsum(l, r, s, m, p * 2);
        }
        if (r > m) {
            sum += getsum(l, r, m + 1, t, p * 2 + 1);
        }
        return sum;
    }
}