线段树

含 lazy 标记 pushdown

struct segtree
{
    struct tree {
        int l, r;
        //maintain something
    }tr[N << 2];
    inline void pushup(int u) {
        //maintain something
    }
    inline void pushdown(tree& node, tree& le, tree* re) {
        //maintain something
    }
    inline void pushdown(int u) {
        //maintain something
    }
    void build(int u, int l, int r) {
        tr[u] = { l,r };  //assign something
        if (l == r) {
            tr[u] = { l,r };  //assign something
            return;
        }
        int mid = l + r >> 1;
        build(ul, l, mid), build(ur, mid + 1, r);
        pushup(u);
    }
    void modify(int u, int l, int r, int v) {
        if (tr[u].l >= l && tr[u].r <= r) {
            //return something
            return;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        if (l <= mid)modify(ul, l, r, v);
        if (r > mid)modify(ur, l, r, v);
        pushup(u);
    }
    int query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) {
            //return something
            return 1;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        int t = 0;
        if (l <= mid)t = query(ul, l, r);
        if (r > mid)t = query(ur, l, r);
        return t;
    }
}tr;
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

树状数组

只维护前缀和，区间sum，注意 n 的范围

struct BIT
{
    int tr[N];
    inline void ub(int& x) { x += x & (-x); }
    inline void db(int& x) { x -= x & (-x); }
    inline void modify(int x, int t) { for (; x <= n; ub(x))tr[x] += t; }
    inline int query(int x) {
        int res = 0;
        for (; x > 0; db(x))res += tr[x];
        return res;
    }
}bt;
1
2
3
4
5
6
7
8
9
10
11
12