线段树

介绍

解决问题类型

  1. 单点修改
  2. 区间修改
  3. 区间查询

建议与提示

  • 不同的操作对应不同的题目类型，有的不需要修改只需要查询，有的不需要查询只需要修改，这类题目一般有简单的做法，比如单调队列的最大值问题
  • 一般的结合律和共享可累计性质的操作，都可以视作线段树里的操作，例如求和、求积、求最值、求最大公约数等
  • 单点修改加上区间求和的题目也可以用树状数组来做，可以参考之前的文章
  • 上述需求的组合，一般使用线段树来做
  • 熟能生巧

写法

本人是Java选手，因此使用Java来实现，其他语言是类似的，这里给出单点修改 + 区间求和的代码以及区间修改 + 区间求和的代码

单点修改 + 区间求和

题目链接 树状数组模板题

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int max(int... a) {
        int res = a[0];
        for (int i : a) res = Math.max(res, i);
        return res;
    }

    static int min(int... a) {
        int res = a[0];
        for (int i : a) res = Math.min(res, i);
        return res;
    }

    static class Read {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer("");

        String next() {
            while (!stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

        int nextInt() {return Integer.parseInt(next());}
        long nextLong() {return Long.parseLong(next());}
    }

    static Read in = new Read();
    static final int N = (int) (5e5 + 5);
    static long[] f = new long[N<<2];
    static int[] a = new int[N];
    static int n, m, q, x, y;

    static void build(int k, int l, int r) {
        if (l == r) {
            f[k] = a[l];
            return;
        }
        int m = (l + r) >> 1;
        build(k<<1, l, m);
        build(k<<1|1, m + 1, r);
        f[k] = f[k<<1] + f[k<<1|1];
    }

    static void update(int k, int l, int r, int x, int c) {
        f[k] += c;
        if (l == r) return;
        int m = (l + r) >> 1;
        if (x <= m) update(k<<1, l, m, x, c);
        else update(k<<1|1, m + 1, r, x, c);
    }

    static long calc(int k, int l, int r, int s, int t) {
        if (l == s && r == t) return f[k];
        int m = (l + r) >> 1;
        if (t <= m) return calc(k<<1, l, m, s, t);
        if (s > m) return calc(k<<1|1, m + 1, r, s, t);
        return calc(k<<1, l, m, s, m) + calc(k<<1|1, m + 1, r, m + 1, t);
    }

    public static void main(String[] args) {
        n = in.nextInt();
        m = in.nextInt();
        for (int i = 1; i <= n; i++) a[i] = in.nextInt();
        build(1, 1, n);
        for (int i = 1; i <= m; i++) {
            q = in.nextInt();
            x = in.nextInt();
            y = in.nextInt();
            if (q == 1) update(1, 1, n, x, y);
            else System.out.println(calc(1, 1, n, x, y));
        }
    }
}

区间修改 + 区间求和

题目链接 线段树模板题

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int max(int... a) {
        int res = a[0];
        for (int i : a) res = Math.max(res, i);
        return res;
    }

    static int min(int... a) {
        int res = a[0];
        for (int i : a) res = Math.min(res, i);
        return res;
    }

    static class Read {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer("");

        String next() {
            while (!stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

        int nextInt() {return Integer.parseInt(next());}
        long nextLong() {return Long.parseLong(next());}
    }

    static Read in = new Read();
    static final int N = 100005;
    static long[] f = new long[N<<2], v = new long[N<<2];
    static int[] a = new int[N];
    static int n, m, q, x, y;
    static long z;

    static void build(int k, int l, int r) {
        if (l == r) {
            f[k] = a[l];
            return;
        }
        int m = (l + r) >> 1;
        build(k<<1, l, m);
        build(k<<1|1, m + 1, r);
        f[k] = f[k<<1] + f[k<<1|1];
    }

    static void update(int k, int l, int r, int x, int y, long z) {
        if (l == x && r == y) {
            v[k] += z;
            return;
        }

        f[k] += (y - x + 1) * z;
        int m = (l + r) >> 1;
        if (y <= m) update(k<<1, l, m, x, y, z);
        else if (x > m) update(k<<1|1, m + 1, r, x, y, z);
        else {
            update(k<<1, l, m, x, m, z);
            update(k<<1|1, m + 1, r, m + 1, y, z);
        }
    }

    static long calc(int k, int l, int r, int s, int t, long p) {
        p += v[k];
        if (l == s && r == t) return p * (t - s + 1) + f[k];
        int m = (l + r) >> 1;
        if (t <= m) return calc(k<<1, l, m, s, t, p);
        else if (s > m) return calc(k<<1|1, m + 1, r, s, t, p);
        return calc(k<<1, l, m, s, m, p) + calc(k<<1|1, m + 1, r, m + 1, t, p);
    }

    public static void main(String[] args) {
        n = in.nextInt();
        m = in.nextInt();
        for (int i = 1; i <= n; i++) a[i] = in.nextInt();
        build(1, 1, n);
        for (int i = 1; i <= m; i++) {
            q = in.nextInt();
            x = in.nextInt();
            y = in.nextInt();
            if (q == 1) {
                z = in.nextLong();
                update(1, 1, n, x, y, z);
            }
            else System.out.println(calc(1, 1, n, x, y, 0));
        }
    }
}