线段树介绍

线段树是一种二叉树结构，用于处理区间查询和更新操作。它将一个区间划分成若干个子区间，并将每个子区间的信息存储在树的节点中。

线段树维护的信息类型
父范围上的某个信息，可以用O(1)的时间，从子范围的信息加工得到。满足的信息类型比如：累加和，最大值，最小值等。不满足的信息类型比如：某范围上出现次数最多的数。

线段树的经典功能，如下操作单次调用的时间复杂度为O(logn)：

  • 范围查询，包括范围内的累加和、最大值、最小值等
  • 范围修改，包括范围内每个数都增加、重置等操作

线段树的范围修改功能，要做到单次调用的时间复杂度为O(logn)的要求：
一段范围上统一进行了某种修改操作，可以用O(1)的时间，从子范围的信息加工得到
满足的情况，比如：一段范围上的每个数都加上一个数，累加和可以快速的加工出来
不满足的情况，比如：这段范围上每个数字都逆序（63->36），累加和就无法快速的加工出来

线段树的组织

线段树组织累加和

  1. 线段树开始下标可以为1，也可以为0，下标从1开始是最经典的设定
  2. 线段树在初始化时，就指定范围的规模[1,n]，一旦确定不能更改
  3. 任何一个大范围[l,r]，严格从中间mid，拆分为[l,mid]和[mid+1,r]两个范围
  4. 每个范围的信息，填写在独立的、连续数组中，最大的范围[1,n],就把信息填写在sum[1]
  5. 如果父范围把信息填写在sum[p]，那么子范围的信息，就填写在sum[p2]和sum[p2+1]中
  6. 范围[l,r]和i值的对应，是由公式限制死的，由递归参数维护，无需去记录对应关系

如果线段树的范围是[1,n]，那么需要开4n的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class SegmentTree {
    public static int MAXN = 1001;
    public static long[] arr = new long[MAXN];
    public static long[] tree = new long[MAXN << 2];

    public static void build(int l, int r, int i) {
        if (l == r) {
            tree[i] = arr[l];
            return;
        }
        int mid = l + (r - l) / 2;
        build(l, mid, i << 1);
        build(mid + 1, r, i << 1 | 1);
        tree[i] = tree[i << 1] + tree[i << 1 | 1];
    }

    public static long query(int jobl, int jobr, int l, int r, int i) {
        if (jobl <= l && jobr >= r) {
            return tree[i];
        }
        int mid = l + (r - l) / 2;
        long ans = 0;
        if (jobl <= mid) {
            ans += query(jobl, jobr, l, mid, i << 1);
        }
        if (jobr > mid) {
            ans += query(jobl, jobr, mid+1, r, i << 1 | 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 50; i++) {
            arr[i] = i;
        }
        build(1, 50, 1);

        System.out.println(query(2,10, 1, 50, 1));
    }
}

懒更新

add操作，将区间[l,r]上的每个数都加上一个数
void add(jobl, jobr, jobv, l, r, i)
前三个是任务参数，表示jobl到jobr的区间上的每个数都加上jobv，递归过程中这三个参数不变
后三个是递归参数，表示当前递归到了l到r的范围，i是当前范围的节点编号，可变

懒更新机制：

  1. 如果发现任务范围(jobl, jobr)把当前范围(l,r)完全覆盖，那么不再向下传递任务，懒住 add[i] += jobv sum[i] += (r-l+1) * jobv
  2. 如果任务范围不能把当前范围全包，把该范围上积攒的懒信息，往下只发一层，down过程。然后决定当前任务是否要去往，左范围，右范围，继续调用子递归过程。子递归完成后，利用左右范围的sum信息，把当前范围的sum[i]信息修改正确，up过程
  3. 退出当前递归过程
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    package com.fms231;

    import java.io.*;

    public class SegmentTree {
        public static int MAXN = 1001;
        public static long[] arr = new long[MAXN];
        public static long[] tree = new long[MAXN << 2];
        public static long[] add = new long[MAXN << 2];

        public static void up(int i) {
            tree[i] = tree[i << 1] + tree[i << 1 | 1];
        }

        public static void down(int i, int ln, int rn) {
            if (add[i] != 0) {
                lazy(i << 1, add[i], ln);
                lazy(i << 1 | 1, add[i], rn);
                add[i] = 0;
            }
        }

        public static void lazy(int i, long v, int n) {
            add[i] += v;
            tree[i] += n * v;
        }

        public static void build(int l, int r, int i) {
            if (l == r) {
                tree[i] = arr[l];
            } else {
                int mid = l + (r - l) / 2;
                build(l, mid, i << 1);
                build(mid + 1, r, i << 1 | 1);
                up(i);
            }
            add[i] = 0;
        }

        public static void add(int jobl, int jobr, long jobv, int l, int r, int i) {
            if (jobl <= l && r <= jobr) {
                lazy(i ,jobv, r - l + 1);
                return;
            }
            int mid = l + (r - l) / 2;
            down(i, mid - l + 1, r - mid);
            if (jobl <= mid) {
                add(jobl, jobr, jobv, l, mid, i << 1);
            }
            if (jobr > mid) {
                add(jobl, jobr, jobv, mid+1, r, i << 1 | 1);
            }
            up(i);
        }

        public static long query(int jobl, int jobr, int l, int r, int i) {
            if (jobl <= l && jobr >= r) {
                return tree[i];
            }
            int mid = l + (r - l) / 2;
            down(i ,mid - l + 1, r - mid);
            long ans = 0;
            if (jobl <= mid) {
                ans += query(jobl, jobr, l, mid, i << 1);
            }
            if (jobr > mid) {
                ans += query(jobl, jobr, mid+1, r, i << 1 | 1);
            }
            return ans;
        }

        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StreamTokenizer in = new StreamTokenizer(br);
            PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

            in.nextToken();
            int n = (int) in.nval;

            in.nextToken();
            int m = (int) in.nval;

            for (int i = 1; i <= n; i++) {
                in.nextToken();
                arr[i] = (long) in.nval;
            }

            long jobv;
            for (int i = 1, op, jobl, jobr; i <= m; i++) {
                in.nextToken();
                op = (int) in.nval;
                in.nextToken();
                jobl = (int) in.nval;
                in.nextToken();
                jobr = (int) in.nval;
                if (op == 1) {
                    in.nextToken();
                    jobv = (long) in.nval;
                    add(jobl, jobr, jobv, 1, n, 1);
                } else {
                    out.println(query(jobl,jobr,1,n,1));
                }
            }
        }
    }

线段树的应用

  • 范围重置
  • 范围增加
  • 范围查询
  • 累加和
  • 区间最大值
  • 区间最小值

注意重置和增加，如果重置，则之前懒住add、sum信息全部清空，更新update、change信息，如果需要向下传递，则先传递update、change更新信息，再传递add信息，然后将当前update、add、sum信息清空。