浅谈线段树（Segment Tree）

线段树的概念与性质展开目录

线段树首先是一棵树，而且是二叉树。树上的每个节点对应于一个区间 [a,b]，a,b 通常为整数。同一层的节点所代表的区间，互相不重叠。并且同一层的区间加起来是连续的区间，叶子节点的区间是单位长度 1，无法再分

例如下图表示的是区间 [1,9] 的线段树
从图上可以看出线段树具有下面几个性质：

每个区间的长度是区间内整数的个数
叶子节点长度为 1，不能再分
若一个节点对应的区间是 [a,b]，则其子节点对应的区间分别是 [a,(a+b)/2] 和 [((a+b)/2)+1,b]（除法去尾取整）
线段树的平分构造实际上是利用二分的方法，若根节点对应的区间是 [a,b]，那么他的深度为 $log_2 (b-a+1)+1$（向上取整）
叶子节点的数目和根节点表示的区间长度相同
线段树节点要么 0 度，要么 2 度，因此若叶子节点数目为 N，则线段树总节点数目为 2N-1
线段树上，任意一个区间被分解后得到的 “终止节点” 数目都是 logn 量级
线段树上更新叶子节点和进行区间分解时间复杂度都是 O (logn) 的

以上结论为线段树能在 O (logn) 的时间内完成插入、更新、查找、统计数据提供了理论依据

线段树的构建展开目录

伪代码

function 以节点idx为根结点，idx对应区间为[l,r]
    对节点idx初始化
    if(l != r)
        以idx的左孩子为根建树，区间为[l,(l+r)>>1]
        以idx的右孩子为根建树，区间为[((l+r)>>1)+1,r]

建树的时间复杂度是 O (n)，n 为根节点对应的区间长度

线段树的基本用途展开目录

线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分，按区间动态进行修改，而且还需要按区间多次查询，那么使用线段树可以达到较快的速度

线段树应用举例展开目录

原题链接：HDU1166

给你一个数列 $A_1,A_2,...,A_n$，并且多次进行下列两个操作：

对数列里面的某个数进行加减
询问这个序列里面任意一个连续的子序列 $A_i,A_{i+1},...,A_j$ 的和是多少

构建一棵线段树，[1,n] 就是根节点对应的区间，在每个节点记录该节点对应的区间内的和 sum

对于操作 1，因为序列里面 $A_i$ 最多只会被线段树的 logn 个节点覆盖。只要求对线段树覆盖的 $A_i$ 所在节点的区间进行操作，因此时间复杂度是 O (logn)

对于操作 2，同样只需要找到区间覆盖的 “终止” 节点，然后把 “终止” 节点的 sum 累加起来，因为这些节点的数量是 logn 的，所以这一步的复杂度也是 O (logn)

走到节点 [l,r] 时，如果要查询的区间就是 [l,r]，那么直接返回该节点的 sum，并累加到总和上；如果不是，则取 mid = (l+r) >> 1，然后看要查询的区间与 [l,mid] 或 [mid+1,r] 哪个有交集，就进入哪个区间进行进一步查询

用线段树解题，关键是要想清楚每个节点要存哪些信息。先建树，然后插入数据，最后更新、查询

每个节点可表示为一个结构体

class Node {
    int l, r, sum;
}

线段树一般可以由左右指针或数组存储，根节点下标为 0，假设线段树某节点为 i，则：

左子节点下标为 (i << 1) + 1
右子节点下表为 (i << 1) + 2

如果根节点区间为 [1,n]

使用左右节点指针，则数组需要有 2n-1 个元素
不适用左右节点指针，则数组需要有 $2*2^{log_2n}-1$ 个元素。由于该值小于等于 4n-1，因此实际运用时常开 4n 大小的数组即可

构造初始线段树由根节点一次往下递归构造，代码如下

static void make(int l, int r, int idx) { // l为左端点，r为右端点，idx为数组下标
    n[idx].l = l;
    n[idx].r = r;
    if (l == r) //已经是叶节点了
        n[idx].sum = t[l]; //也可以是t[r]
    else {
        make(l,(l + r) >> 1,(idx << 1) + 1); //递归构造左子树
        make(((l + r) >> 1) + 1, r, (idx << 1) + 2); //递归构造右子树
        n[idx].sum = n[(idx << 1) + 1].sum + n[(idx << 1) + 2].sum;
        //父节点值等于子节点值之和，线段树分成两段
    }
}

t 数组存放输入的初始值。当总数为 n 时，执行 make (1,n,0)，输入样例得到的额线段树如下图所示
当第 idx 个营地增加 j 个人时，从根节点 n [0] 开始，不断往下递归更改人数，即只要包含改点 idx 的线段都增加相应的人数 j，代码如下

static void add(int i, int j, int idx) { // 第i个营地增加j个人
    // 从根节点不断往下更改，只要包含点i的线段都增加数量j
    n[idx].sum += j;
    if (n[idx].l == i && n[idx].r == i) // 如果找到i的叶子节点则停止
        return;
    if (i <= ((n[idx].l + n[idx].r) >> 1)) // 如果i在线段左边
        add(i, j, (idx << 1) + 1); // 递归进入左子节点
    else // 如果i在线段右边
        add(i, j, (idx << 1) + 2); // 递归进入右子节点
}

同理，当第 i 个营地减少 j 个人时，代码如下

static void sub(int i, int j, int idx) { // 第i个营地减少j个人
    // 从根节点不断往下更改，只要包含点i的线段都减少数量j
    n[idx].sum -= j;
    if (n[idx].l == i && n[idx].r == i) // 如果找到i的叶子节点则停止
        return;
    if (i <= ((n[idx].l + n[idx].r) >> 1)) //如果i在线段左边
        sub(i, j, (idx << 1) + 1); // 递归进入左子节点
    else
        sub(i, j, (idx << 1) + 2); // 递归进入右子节点
}

询问从 [l,r] 区间内的营地人数代码如下

static void query(int l, int r, int idx) { // 初始idx为0，即从根节点开始查找
    if (l <= n[idx].l && r >= n[idx].r)
        SUM += n[idx].sum;
    else {
        int mid = (n[idx].l + n[idx].r) >> 1;
        if (r <= mid) // 要查询的区间在左边
            query(l, r, (idx << 1) + 1);
        else if (l > mid) // 要查询的区间在右边
            query(l, r, (idx << 1) + 2);
        else { // 要查询的区间在中间，分段查询，左右都查
            query(l, r, (idx << 1) + 1);
            query(l, r, (idx << 1) + 2);
        }
    }
}

这段代码可以这么理解，假设要查询的区间为 [l,r]，当前走到的节点对应的区间是 [n [idx].l,n [idx].r]，如果 $[n [idx].l,n [idx].r]\in [l,r]$，则将当前区间的信息记录下来，例如求区间和，就将当前区间和的信息累加到 SUM 中；如果要查询区间的右端点 r<= 当前区间的中点，说明需要查询的区间就在左子树里；反之，如果要查询区间的左端点 l > 当前区间的终点，说明要查询的区间就在右子树里；如果上面两种情况都不满足，说明左右子树均有需要的信息，左右子树都要查

完整代码如下

import java.util.Scanner;

public class Main {
    static Node[] n;
    static int[] t;
    static int SUM;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        for (int p = 1; p <= T; p++) {
            int tmp = 0;
            int N = cin.nextInt();
            n = new Node[4 * N];
            t = new int[N + 1];
            for (int i = 1; i <= N; i++)
                t[i] = cin.nextInt();
            make(1, N, 0);
            while (true) {
                String str = cin.next();
                if ("End".equals(str))
                    break;
                int i = cin.nextInt();
                int j = cin.nextInt();
                if ("Query".equals(str)) {
                    SUM = 0;
                    if (tmp == 0) {
                        System.out.println("Case " + p + ":");
                        tmp++;
                    }
                    query(i, j, 0);
                    System.out.println(SUM);
                } else if ("Add".equals(str))
                    add(i, j, 0);
                else // Sub
                    sub(i, j, 0);
            }
        }
    }

    static void make(int l, int r, int idx) { // l为左端点，r为右端点，idx为数组下标
        n[idx] = new Node();
        n[idx].l = l;
        n[idx].r = r;
        if (l == r) // 已经是叶节点了
            n[idx].sum = t[l]; // 也可以是t[r]
        else {
            make(l, (l + r) >> 1, (idx << 1) + 1); // 递归构造左子树
            make(((l + r) >> 1) + 1, r, (idx << 1) + 2); // 递归构造右子树
            n[idx].sum = n[(idx << 1) + 1].sum + n[(idx << 1) + 2].sum;
            // 父节点值等于子节点值之和，线段树分成两段
        }
    }

    static void add(int i, int j, int idx) { // 第i个营地增加j个人
        // 从根节点不断往下更改，只要包含点i的线段都增加数量j
        n[idx].sum += j;
        if (n[idx].l == i && n[idx].r == i) // 如果找到i的叶子节点则停止
            return;
        if (i <= ((n[idx].l + n[idx].r) >> 1)) // 如果i在线段左边
            add(i, j, (idx << 1) + 1); // 递归进入左子节点
        else // 如果i在线段右边
            add(i, j, (idx << 1) + 2); // 递归进入右子节点
    }

    static void sub(int i, int j, int idx) { // 第i个营地减少j个人
        // 从根节点不断往下更改，只要包含点i的线段都减少数量j
        n[idx].sum -= j;
        if (n[idx].l == i && n[idx].r == i) // 如果找到i的叶子节点则停止
            return;
        if (i <= ((n[idx].l + n[idx].r) >> 1)) // 如果i在线段左边
            sub(i, j, (idx << 1) + 1); // 递归进入左子节点
        else
            sub(i, j, (idx << 1) + 2); // 递归进入右子节点
    }

    static void query(int l, int r, int idx) { // 初始idx为0，即从根节点开始查找
        if (l <= n[idx].l && r >= n[idx].r)
            SUM += n[idx].sum;
        else {
            int mid = (n[idx].l + n[idx].r) >> 1;
            if (r <= mid) // 要查询的区间在左边
                query(l, r, (idx << 1) + 1);
            else if (l > mid) // 要查询的区间在右边
                query(l, r, (idx << 1) + 2);
            else { // 要查询的区间在中间，分段查询，左右都查
                query(l, r, (idx << 1) + 1);
                query(l, r, (idx << 1) + 2);
            }
        }
    }
}

class Node {
    int l, r, sum;
}

关于线段树的更多习题见线段树例题

单点更新
HDU 1166 敌兵布阵
 HDU 1754 I Hate It
POJ 3264 Balanced Lineup
HDU 1394 Minimum Inversion Number
HDU 2795 Billboard
POJ 2352 Stars
POJ 2481 Cows
POJ 3067 Japan
CF 6E Exposition

区间更新
HDU 1698 Just a Hook
HDU 1556 Color the ball
ZOJ 1610 Count the Colors
POJ 2528 Mayor's posters
Ural 1019 A Line Painting

Catalog

浅谈线段树（Segment Tree）

January 6, 2019 • Read: 10046 • 算法 • 阅读设置

线段树的概念与性质展开目录

线段树的构建展开目录

线段树的基本用途展开目录

线段树应用举例展开目录