小花生

study & life record.

线段树_v2

发表于 分类于 ，

线段树模板整理。

Segment Tree

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
template<class Info>
struct SegmentTree {
    int n;
    vector<Info> info;

    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector<Info>(n_, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }

    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }

    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }

    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y);
    }
};

struct Info {
    // Maintained value
    // Constructed value
};

Info operator+(const Info &a, const Info &b){
    Info c;
    // Overloaded operation
    return c;
}

维护区间和，实现单点修改，区间查询

1
2
3
4
5
6
7
8
9
10
struct Info {
    int sum;
    Info(int _sum = 0) : sum(_sum) {};
};

Info operator+(const Info &a, const Info &b){
    Info c;
    c.sum = a.sum + b.sum;
    return c;
}

维护区间 GCD，实现单点修改，区间查询

1
2
3
4
5
6
7
8
9
10
struct Info {
    int gcd;
    Info(int _gcd = 0) : gcd(_gcd) {};
};

Info operator+(const Info &a, const Info &b){
    Info c;
    c.gcd = __gcd(a.gcd, b.gcd);
    return c;
}

维护最大子段和，实现单点修改，区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 维护该区间内的 总和，最大前缀和，最大后缀和，最大子段和
constexpr int inf = 1e18;
struct Info {
    int sum;
    int prefix;
    int suffix;
    int ans;

    Info() : sum(0), prefix(-inf), suffix(-inf), ans(-inf) {}
    Info(int x) : sum(x), prefix(x), suffix(x), ans(x) {}
};

Info operator+(const Info &a, const Info &b){
    Info c;
    c.sum = a.sum + b.sum;
    c.prefix = max(a.prefix, a.sum + b.prefix);
    c.suffix = max(b.suffix, b.sum + a.suffix);
    c.ans = max({a.ans, b.ans, a.suffix + b.prefix});
    return c;
}

维护区间 GCD，实现区间加，区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// gcd(a[l], a[l + 1], ..., a[r]) = gcd(a[l], a[l + 1] - a[l], ..., a[r] - a[r - 1])
// 考虑差分序列 cf[i] = a[i] - a[i - 1]
// 这样[l, r]上的 gcd 就可以表示为 gcd(sum[0, 1, ... l], gcd(cf[l + 1], ..., cf[r]))
// 综上, 维护差分序列的 sum, gcd 即可

// 注意 modify 更新方式需要变化:
info[p].sum += v.sum, info[p].gcd += v.sum;

struct Info {
    int sum, gcd;
    Info() : sum(0), gcd(0) {}
    Info(int x) : sum(x), gcd(x) {}
};

Info operator+(const Info &a, const Info &b){
    Info c;
    c.sum = a.sum + b.sum;
    c.gcd = __gcd(a.gcd, b.gcd);
    return c;
}

Lazy Segment Tree

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
106
template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;

    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector<Info>(n_, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        tag.assign(4 << __lg(n), Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }

    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }

    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }

    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }

    void modify(int l, int r, const Tag &v) {
        return modify(1, 0, n, l, r, v);
    }
    void modify(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        modify(2 * p, l, m, x, y, v);
        modify(2 * p + 1, m, r, x, y, v);
        pull(p);
    }

    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y);
    }

};

struct Tag {
    // Maintained value
    // Constructed value
    void apply(const Tag &t) & {
        // Apply
    }
};

struct Info {
    // Maintained value
    // Constructed value
    void apply(const Tag &t) & {
        // Apply
    }
};

Info operator+(const Info &a, const Info &b) {
    Info c;
    // Overloaded operation
    return c;
}

维护区间和，实现区间加，区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Tag {
    int add;
    Tag(int _add = 0) : add(_add) {};
    void apply(const Tag &t) & {
        add += t.add;
    }
};

struct Info {
    int sum, len;
    Info(int _sum = 0, int _len = 1) : sum(_sum), len(_len) {};
    void apply(const Tag &t) & {
        sum += t.add * len;
    }
};

Info operator+(const Info &a, const Info &b) {
    Info c;
    c.sum = a.sum + b.sum;
    c.len = a.len + b.len;
    return c;
}

维护区间和，实现区间加，区间乘，区间查询

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
struct Tag {
    int add, mul;
    Tag() : add(0), mul(1) {}
    Tag(int x, int y) : add(x), mul(y) {}
    
    void apply(const Tag &t) & {
        add = (add * t.mul + t.add) % p;
        mul = (mul * t.mul) % p;
    }
};

struct Info {
    int sum, len;
    Info() : sum(0), len(0) {}
    Info(int x, int _len = 1) : sum(x), len(_len) {}
    void apply(const Tag &t) & {
        sum = (sum * t.mul + t.add * len) % p;
    }
};

Info operator+(const Info &a, const Info &b) {
    Info c;
    c.len = a.len + b.len;
    c.sum = (a.sum + b.sum) % p;
    return c;
}