• 对于一个数组，如果想要动态的管理它，就使用线段树把

区间加 & Sum

区间修改， 区间加和求和

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
template<typename T>
struct Segment {
    vector<T> f;
    vector<T> tag;
    int n;

    Segment() {}
    Segment(int n) : n(n) { 
        f.assign(n << 2 + 1, 0);
        tag.assign(n << 2 + 1, 0);
    } 

    void update(int l, int r, T c, int s, int t, int p) {
        if (l <= s && t <= r) {
            f[p] += c * (t - s + 1);
            tag[p] += c;
            return;
        }

        int m = s + ((t - s) >> 1);
        
        if (tag[p]) {
            pushdown(s, t, p);
        }
        
        if (l <= m) {
            update(l, r, c, s, m, p * 2);
        } 
        if (r > m) {
            update(l, r, c, m + 1, t, p * 2 + 1);
        }
        f[p] = f[p * 2] + f[p * 2 + 1];
    }

    void pushdown(int s, int t, int p) {
        int m = s + ((t - s) >> 1);
        f[p * 2] += 1LL * (m - s + 1) * tag[p];
        f[p * 2 + 1] += 1LL * (t - m) * tag[p];
        tag[p * 2] += tag[p];
        tag[p * 2 + 1] += tag[p];
        tag[p] = 0;
    }

    T query(int l, int r, int s, int t, int p) {
        if (l <= s && t <= r) {
            return f[p];
        }

        int m = s + ((t - s) >> 1);
        if (tag[p]) {
            pushdown(s, t, p);
        }

        T sum = 0;
        if (l <= m) {
            sum += query(l, r, s, m, p * 2);
        } 
        if (r > m) {
            sum += query(l, r, m + 1, t, p * 2 + 1);
        }
        return sum;
    }

    T query(int s, int t) {
        return query(s, t, 1, n, 1);
    }

    void update(int s, int t, T c) {
        update(s, t, c, 1, n, 1);
    }
};
  • 我赶时间版本：
    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
    template<typename T>
    struct Segment {
        vector<T> f;
        int n;

        Segment() {}
        Segment(int n) : n(n) { 
            f.assign(n << 2 + 1, 0);
        } 

        void pushup(int s, int t, int p) {

        }

        void update(int l, int r, T c, int s, int t, int p) {
            if (s == t && l == s) {
                f[p] = c;
                return;
            }

            int m = s + ((t - s) >> 1);
            
            if (l <= m) {
                update(l, r, c, s, m, p * 2);
            } 
            if (r > m) {
                update(l, r, c, m + 1, t, p * 2 + 1);
            }
            pushup(s, t, p);
        }


        T query(int l, int r, int s, int t, int p) {
            if (l <= s && t <= r) {
                return f[p];
            }

            int m = s + ((t - s) >> 1);

            T sum = 0;
            if (l <= m) {
                sum += query(l, r, s, m, p * 2);
            } 
            if (r > m) {
                sum += query(l, r, m + 1, t, p * 2 + 1);
            }
            return sum;
        }

        T query(int s, int t) {
            return query(s, t, 1, n, 1);
        }

        void update(int s, int t, T c) {
            update(s, t, c, 1, n, 1);
        }
    };