树状数组

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
struct BIT {
    #define lowbit(x) (x & (-x))

    int n;
    vector<int> tree;

    BIT (int n) {
        this->n = n;
        tree.resize(n + 1);
    }

    void add(int x, int a) {
        for (int i = x; i <= n; i += lowbit(i)) {
            tree[i] += a;
        }
    }

    int sum(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) {
            res += tree[i];
        }
        return res;
    }

    int rangeSum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

  • 树状数组求逆序对

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int getinv(vector<int> a) {
        vector<int> dec = a;
        sort(dec.begin(), dec.end());
        dec.erase(unique(dec.begin(), dec.end()), dec.end());
        auto find = [&](int x) -> int {
            return lower_bound(dec.begin(), dec.end(), x) - dec.begin() + 1;
        };
        int n = a.size();
        BIT bit(n);
        int res = 0;
        for (int x : a) {
            x = find(x);
            res += bit.rangeSum(x, n);
            bit.add(x, 1);
        }
        return res;
    }

线段树

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 SegTree {
    #define lson (rt << 1)
    #define rson (rt << 1 | 1)

    int n;
    vector<T> info;

    SegTree() {}
    SegTree(vector<T> _init) {
        init(_init);
    }

    void init(vector<T> _init) {
        n = _init.size() - 1;
        info.assign(n << 2, T());
        auto build = [&](auto self, int rt, int l, int r) -> void {
            if (l == r) {
                info[rt] = _init[l];
                return;
            }
            int m = l + r >> 1;
            self(self, lson, l, m);
            self(self, rson, m + 1, r);
            push_up(rt);
        };
        build(build, 1, 1, n);
    }

    void push_up(int rt) {
        info[rt] = info[lson] + info[rson];
    }

    void modify(int rt, int l, int r, int x, const T& v) {
        if (l == r) {
            info[rt] = v;
            return;
        }
        int m = l + r >> 1;
        if (x <= m) modify(lson, l, m, x, v);
        else modify(rson, m + 1, r, x, v);
        push_up(rt);
    }

    void modify(int x, const T& v) {
        modify(1, 1, n, x, v);
    }

    T rangeQuery(int rt, int l, int r, int x, int y) {
        if (l < 1 || x > r || y < l || r > n) {
            return T();
        }
        if (l >= x && r <= y) {
            return info[rt];
        }
        int m = l + r >> 1;
        return rangeQuery(lson, l, m, x, y) + rangeQuery(rson, m + 1, r, x, y);
    }

    T rangeQuery(int l, int r) {
        return rangeQuery(1, 1, n, l, r);
    }
};


struct Node {
};


Node operator+ (const Node& a, const Node& b) {
}

ST 表（RMQ）

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
struct RMQ {
    int n;
    vector<int> Logn;
    vector<vector<int>> f;

    RMQ() {}
    RMQ(vector<int> vec) {
        n = vec.size() - 1;
        Logn.resize(n + 1), f.resize(n + 1);
        init(vec);
    }

    void init(vector<int> vec) {
        Logn[1] = 0;
        for (int i = 2; i <= n; i++) {
            Logn[i] = Logn[i >> 1] + 1;
        }
        for (int i = 0; i <= n; i++) {
            f[i].resize(30);
            f[i][0] = vec[i];
        }

        for (int j = 1; (1 << j) <= n; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int query(int l, int r) {
        int d = Logn[r - l + 1];
        return max(f[l][d], f[r - (1 << d) + 1][d]);
    }
};

评论区仅供交流，有问题请提 issue 反馈。