线段树

发表于 更新于

一、算法实现

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
typedef long long LLI;
const int maxn = 120015;
const int maxn4 = maxn << 2;

struct SegTree {
    LLI tree[maxn4];
    LLI lazy[maxn4];
    void build() {
        memset(tree, 0, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
    }
    void pushdown(int rt, int s, int t, int mid) {
        tree[rt << 1] += lazy[rt] * (mid - s + 1);
        lazy[rt << 1] += lazy[rt];
        tree[rt << 1 | 1] += lazy[rt] * (t - mid);
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0; // clear lazy-flag
    }
    void range_add(int rt, LLI val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            tree[rt] += (t - s + 1) * val;
            lazy[rt] += val;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) range_add(rt << 1, val, l, r, s, mid);
        if (r > mid) range_add(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
    }
    LLI query(int rt, int l, int r, int s, int t) {
        if (l <= s && r >= t) return tree[rt];
        LLI ans = 0;
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) ans += query(rt << 1, l, r, s, mid);
        if (r > mid) ans += query(rt << 1 | 1, l, r, mid + 1, t);
        return ans;
    }
};

2、区间最值模板(不支持0)

大部分情况，都可以将数据离散化一个不在0的区间内，此时应该减少不必要的判断，避免题目卡时间：

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
const int maxn = 100010;
const int maxn4 = 100010 * 4;

typedef int LLI;
struct SegTree {
    LLI tree[maxn4];
    LLI lazy[maxn4];
    void clear() {
        memset(tree, -1, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
    }
    void pushdown(int rt, int s, int t, int mid) {
        // unsupport zero update!
        if (lazy[rt]) {
            tree[rt << 1] = lazy[rt];
            lazy[rt << 1] = lazy[rt];
            tree[rt << 1 | 1] = lazy[rt];
            lazy[rt << 1 | 1] = lazy[rt];
            lazy[rt] = 0; // clear lazy-flag
        }
    }
    // example: (1,val,l,r,1,N);
    void update(int rt, LLI val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            tree[rt] = val;
            lazy[rt] = val;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) update(rt << 1, val, l, r, s, mid);
        if (r > mid) update(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
    }
    LLI query(int rt, int l, int r, int s, int t) {
        if (l <= s && r >= t) return tree[rt];
        LLI ans = -1;
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) ans = max(query(rt << 1, l, r, s, mid), ans);
        if (r > mid) ans = max(query(rt << 1 | 1, l, r, mid + 1, t), ans);
        return ans;
    }
};

3、区间最值模板(支持0)

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
const int maxn = 100010;
const int maxn4 = 100010 * 4;

typedef int LLI;
struct SegTree {
    LLI tree[maxn4];
    LLI lazy[maxn4];
    // support zero update!
    bool changed[maxn4];

    void clear() {
        memset(tree, -1, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
        memset(changed, 0, sizeof(changed));
    }
    void pushdown(int rt, int s, int t, int mid) {
        if (changed[rt]) {
            tree[rt << 1] = lazy[rt];
            lazy[rt << 1] = lazy[rt];
            tree[rt << 1 | 1] = lazy[rt];
            lazy[rt << 1 | 1] = lazy[rt];
            lazy[rt] = 0;       // clear lazy-flag
            changed[rt] = 0;    // clear changed-flag
        }
    }
    // example: (1,val,l,r,1,N);
    void update(int rt, LLI val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            tree[rt] = val;
            lazy[rt] = val;
            changed[rt] = 1;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) update(rt << 1, val, l, r, s, mid);
        if (r > mid) update(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
    }
    LLI query(int rt, int l, int r, int s, int t) {
        if (l <= s && r >= t) return tree[rt];
        LLI ans = -1;
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) ans = max(query(rt << 1, l, r, s, mid), ans);
        if (r > mid) ans = max(query(rt << 1 | 1, l, r, mid + 1, t), ans);
        return ans;
    }
};

4、区间最值模板(同时支持区间修改和区间增加)

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
// https://www.luogu.com.cn/problem/P1253
// 注意pushdown函数的实现
const int maxn = 1000010;
const int maxn4 = 1000010 * 4;


struct SegTree {
    LLI tree[maxn4];
    LLI lazy[maxn4];
    LLI diff[maxn4];
    // support zero update!
    bool changed[maxn4];

    void clear() {
        memset(tree, 0, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
        memset(diff, 0, sizeof(diff));
        memset(changed, 0, sizeof(changed));
    }
    void pushdown(int rt, int s, int t, int mid) {
        if (changed[rt]) {
            tree[rt << 1] = lazy[rt];
            lazy[rt << 1] = lazy[rt];
            // 不能漏了这里
            diff[rt << 1] = 0;
            changed[rt << 1] = 1;

            tree[rt << 1 | 1] = lazy[rt];
            lazy[rt << 1 | 1] = lazy[rt];
            // 不能漏了这里
            diff[rt << 1 | 1] = 0;
            changed[rt << 1 | 1] = 1;

            lazy[rt] = 0;       // clear lazy-flag
            changed[rt] = 0;    // clear changed-flag
        }
        if (diff[rt]) {
            tree[rt << 1] += diff[rt];
            diff[rt << 1] += diff[rt];
            tree[rt << 1 | 1] += diff[rt];
            diff[rt << 1 | 1] += diff[rt];
            diff[rt] = 0;       // clear diff-flag
        }
    }
    // example: (1,val,l,r,1,N);
    void update(int rt, LLI val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            diff[rt] = 0;
            tree[rt] = val;
            lazy[rt] = val;
            changed[rt] = 1;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) update(rt << 1, val, l, r, s, mid);
        if (r > mid) update(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
    }
    void range_add(int rt, LLI val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            diff[rt] += val;
            tree[rt] += val;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) range_add(rt << 1, val, l, r, s, mid);
        if (r > mid) range_add(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
    }
    LLI query(int rt, int l, int r, int s, int t) {
        if (l <= s && r >= t) return tree[rt];
        LLI ans = -9223372036854775807LL;
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) ans = max(query(rt << 1, l, r, s, mid), ans);
        if (r > mid) ans = max(query(rt << 1 | 1, l, r, mid + 1, t), ans);
        return ans;
    }
};

5、区间最值模板(最终版)

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
template<typename T, int MAX_N>
struct SegTree {
    T tree[MAX_N*4+4];
    T lazy[MAX_N*4+4];
    // support zero update!
    bool changed[MAX_N*4+4];
    void clear() {
        memset(tree, 0, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
        memset(changed, 0, sizeof(changed));
    }
    void pushdown(int rt, int s, int t, int mid) {
        if (changed[rt]) {
            tree[rt << 1] = lazy[rt];
            lazy[rt << 1] = lazy[rt];
            tree[rt << 1 | 1] = lazy[rt];
            lazy[rt << 1 | 1] = lazy[rt];
            lazy[rt] = 0;       // clear lazy-flag
            changed[rt] = 0;    // clear changed-flag
        }
    }
    void update(T val, int l, int r){
        update(1, val, l, r, 1, MAX_N);
    }
    T query(int l, int r){
        return query(1, l, r, 1, MAX_N);
    }
    // example: (1,val,l,r,1,N);
    void update(int rt, T val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            tree[rt] = val;
            lazy[rt] = val;
            changed[rt] = 1;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) update(rt << 1, val, l, r, s, mid);
        if (r > mid) update(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
    }
    T query(int rt, int l, int r, int s, int t) {
        if (l <= s && r >= t) return tree[rt];
        T ans = -1;
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) ans = max(query(rt << 1, l, r, s, mid), ans);
        if (r > mid) ans = max(query(rt << 1 | 1, l, r, mid + 1, t), ans);
        return ans;
    }
};

5、区间修改区间求和(最终版)

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
template<typename T, int MAX_N>
struct SegTree {
    T tree[MAX_N*4+4];
    T lazy[MAX_N*4+4];
    T diff[MAX_N*4+4];
    // support zero update!
    bool changed[MAX_N*4+4];

    void clear() {
        memset(tree, 0, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
        memset(diff, 0, sizeof(diff));
        memset(changed, 0, sizeof(changed));
    }
    void pushdown(int rt, int s, int t, int mid) {
        if (changed[rt]) {
            tree[rt << 1] = lazy[rt] * (mid - s + 1);
            lazy[rt << 1] = lazy[rt];
            // 不能漏了这里
            diff[rt << 1] = 0;
            changed[rt << 1] = 1;

            tree[rt << 1 | 1] = lazy[rt] * (t - mid);
            lazy[rt << 1 | 1] = lazy[rt];
            // 不能漏了这里
            diff[rt << 1 | 1] = 0;
            changed[rt << 1 | 1] = 1;

            lazy[rt] = 0;       // clear lazy-flag
            changed[rt] = 0;    // clear changed-flag
        }
        if (diff[rt]) {
            tree[rt << 1] += diff[rt] * (mid - s + 1);
            diff[rt << 1] += diff[rt];
            tree[rt << 1 | 1] += diff[rt] * (t - mid);
            diff[rt << 1 | 1] += diff[rt];
            diff[rt] = 0;       // clear diff-flag
        }
    }
    // example: (1,val,l,r,1,N);
    void update(int rt, T val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            diff[rt] = 0;
            tree[rt] = (t - s + 1) * val;;
            lazy[rt] = val;
            changed[rt] = 1;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) update(rt << 1, val, l, r, s, mid);
        if (r > mid) update(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
    }
    void add(int rt, T val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            diff[rt] += val;
            tree[rt] += (t - s + 1) * val;;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) add(rt << 1, val, l, r, s, mid);
        if (r > mid) add(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
    }
    T query(int rt, int l, int r, int s, int t) {
        if (l <= s && r >= t) return tree[rt];
        T ans = 0;
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) ans += query(rt << 1, l, r, s, mid);
        if (r > mid) ans += query(rt << 1 | 1, l, r, mid + 1, t);
        return ans;
    }

    void update(T val, int l, int r){
        update(1, val, l, r, 1, MAX_N);
    }
    void add(T val, int l, int r){
        add(1, val, l, r, 1, MAX_N);
    }
    T query(int l, int r){
        return query(1, l, r, 1, MAX_N);
    }
};