Karrrrrr's 线段树

  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
107
108
109
110

// 线段树
template<typename T = int>
class SegTree {
private:
    class Node {
    public:
        int l = 0;
        int r = 0;
        T val, lazy = 0;
    };

    void _add(int id, int l, int r, T x) {
        if (nodes[id].l > r || nodes[id].r < l) return;

        if (nodes[id].l >= l && nodes[id].r <= r) {
            nodes[id].lazy += x;
            nodes[id].val += (nodes[id].r - nodes[id].l + 1) * x;
            return;
        }

        pushDown(id);
        _add(id << 1, l, r, x);
        _add(id << 1 | 1, l, r, x);
        pushUp(id);
    }

    ll _query(int id, int l, int r) {
        if (nodes[id].l > r || nodes[id].r < l) return 0;
        if (nodes[id].l >= l && nodes[id].r <= r) {
            return nodes[id].val;
        }
        pushDown(id);
        return _query(id << 1, l, r) + _query(id << 1 | 1, l, r);
    }

    void pushUp(int id) {
        nodes[id].val = nodes[id << 1].val + nodes[id << 1 | 1].val;
    }

    void pushDown(int id) {
        if (nodes[id].lazy) {
            nodes[id << 1].lazy += nodes[id].lazy;
            nodes[id << 1].val += nodes[id].lazy * (nodes[id << 1].r - nodes[id << 1].l + 1);
            nodes[id << 1 | 1].lazy += nodes[id].lazy;
            nodes[id << 1 | 1].val += nodes[id].lazy * (nodes[id << 1 | 1].r - nodes[id << 1 | 1].l + 1);
            nodes[id].lazy = 0;
        }

    }
public:
    vector<Node> nodes;
    
    // 初始化线段树长度, 如果需要初始化值, 那么调用带参build, 不然调用无参build
    SegTree(int n) {
        nodes.resize(n << 2);
        // build(1, 1, n);
    }
    // 允许传入一个vector
    void build(int id, int l, int r, vector<T> &data) {
        nodes[id].l = l;
        nodes[id].r = r;

        if (l == r) {
            nodes[id].val = data[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid,data);
        build(id << 1 | 1, mid + 1, r,data);
        pushUp(id);
    }
    // 允许传入一个C数组
    void build(int id, int l, int r, T* &data) {
        nodes[id].l = l;
        nodes[id].r = r;

        if (l == r) {
            nodes[id].val = data[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid,data);
        build(id << 1 | 1, mid + 1, r,data);
        pushUp(id);
    }
    
    

    void build(int id, int l, int r) {
        nodes[id].l = l;
        nodes[id].r = r;
        nodes[id].val = 0;

        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }

    void add(int left, int right, T x) {
        _add(1, left, right, x);
    }


    T query(int left, int right) {
        return _query(1, left, right);
    }
};

 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>
class GCDTree {

    class Node {
    public:
        ll val;
        int l, r;
    };
    
    vector<Node> nodes;
    
    ll _query(int id, int ql, int qr) {
        if (qr < nodes[id].l || ql > nodes[id].r) return 0;
        if (ql <= nodes[id].l && nodes[id].r <= qr) return nodes[id].val;
        return gcd(_query(id << 1, ql, qr), _query(id << 1 | 1, ql, qr));
    }

    void _update(int id, int pos, ll val) {
        if (pos < nodes[id].l || pos > nodes[id].r) return;
        if (nodes[id].l == nodes[id].r) {
            nodes[id].val += val;
            return;
        }
        _update(id << 1, pos, val);
        _update(id << 1 | 1, pos, val);
        pushUp(id);
    }

public:

    void init(int n) {
        nodes.resize(n << 2);
        build(1, 1, n);
    }

    void build(int id, int l, int r) {
        nodes[id].l = l;
        nodes[id].r = r;
        if (l == r) return;

        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }

    void pushUp(int id) {
        nodes[id].val = gcd(nodes[id << 1].val,nodes[id << 1 | 1].val);
    }
    
    void update(int pos, ll val) {
        _update(1, pos, val);
    }

    ll query(int ql, int qr) {
        return _query(1, ql, qr);
    }
};

 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

// 线段树
template<typename T = int>
class SegTree {
private:
    class Node {
    public:
        ll l = 0;
        ll r = 0;
        T val, lazy = 0;
    };

    void _add(int id, int l, int r, T x) {
        if (nodes[id].l > r || nodes[id].r < l) return;

        if (nodes[id].l >= l && nodes[id].r <= r) {
            nodes[id].lazy += x;
            pushUp(id);
            return;
        }
        // 不需要pushDown
        // pushDown(id);
        _add(id << 1, l, r, x);
        _add(id << 1 | 1, l, r, x);
        pushUp(id);
    }

    ll _query(int id, int l, int r) {
        if (nodes[id].l > r || nodes[id].r < l) return 0;
        if (nodes[id].l >= l && nodes[id].r <= r) {
            return nodes[id].val;
        }
        return _query(id << 1, l, r) + _query(id << 1 | 1, l, r);
    }

    void pushUp(int id) {
        if (nodes[id].lazy > 0) {
            nodes[id].val = nodes[id].r - nodes[id].l + 1;
        } else {
            // 这里必须特判, 不然可能会re
            // 叶子节点的时候, id*2会越界
            if (nodes[id].l != nodes[id].r) {
                nodes[id].val = nodes[id << 1].val + nodes[id << 1 | 1].val;
            } else {
                nodes[id].val = 0;
            }
        }
    }

    void pushDown(int id) {
        return;
    }

public:
    vector<Node> nodes;
    
    SegTree(int n) {
        nodes.resize(n << 2);
    }

    void build(int id, int l, int r) {
        nodes[id].l = l;
        nodes[id].r = r;
        nodes[id].val = 0;

        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }

    void add(int left, int right, T x) {
        _add(1, left, right, x);
    }


    T query(int left, int right) {
        return _query(1, left, right);
    }
};

  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
107
108
109
110
111
112

// 区间最值线段树
template<typename T, typename CMP>
class RmqSegTree {
private:
    CMP cmp;

    class Node {
    public:
        int l = 0;
        int r = 0;
        T val = 0;
    };

    void _update(int id, int l, int r, T x) {
        if (nodes[id].l > r || nodes[id].r < l) return;

        if (nodes[id].l >= l && nodes[id].r <= r) {
            nodes[id].val = x;
            return;
        }

        _update(id << 1, l, r, x);
        _update(id << 1 | 1, l, r, x);
        pushUp(id);
    }

    ll _query(int id, int l, int r) {
        if (nodes[id].l > r || nodes[id].r < l) return 0;
        if (nodes[id].l >= l && nodes[id].r <= r) {
            return nodes[id].val;
        }
        return cmp(_query(id << 1, l, r), _query(id << 1 | 1, l, r));
    }

    void pushUp(int id) {
        nodes[id].val = cmp(nodes[id << 1].val, nodes[id << 1 | 1].val);
    }


public:
    vector<Node> nodes;

    // 初始化线段树长度, 如果需要初始化值, 那么调用带参build, 不然调用无参build
    RmqSegTree(int n) {
        nodes.resize(n << 2);
    }

    // 允许传入一个vector
    void build(int id, int l, int r, vector<T> &data) {
        nodes[id].l = l;
        nodes[id].r = r;

        if (l == r) {
            nodes[id].val = data[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid, data);
        build(id << 1 | 1, mid + 1, r, data);
        pushUp(id);
    }

    // 允许传入一个C数组
    void build(int id, int l, int r, T *&data) {
        nodes[id].l = l;
        nodes[id].r = r;

        if (l == r) {
            nodes[id].val = data[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid, data);
        build(id << 1 | 1, mid + 1, r, data);
        pushUp(id);
    }


    void build(int id, int l, int r) {
        nodes[id].l = l;
        nodes[id].r = r;
        nodes[id].val = 0;

        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }

    void update(int left, int right, T x) {
        _update(1, left, right, x);

    }

    T query(int left, int right) {
        return _query(1, left, right);
    }
};

const int N = 2e6 + 10;

struct CMP {
public:
    auto operator()(auto x, auto y) {
        return max(x, y);
    }
};

RmqSegTree<int, CMP> tree(N);