树状数组

模版

一维二维权值树状数组-全局第 k 小

单点修改-区间查询区间修改-区间查询

结构体

C++
int lowbit(const int x) {
    return x & -x;
}
template<class T>
struct FenwickTree {
    vector<T> sum;
    int size;
    FenwickTree() {}
    FenwickTree(int n) {
        resize(n);
    }
    void resize(int n) {
        sum.resize(n + 1);
        size = n;
    }
    void clear() {
        sum.resize(0);
        sum.resize(size + 1);
    }
    T query(int x) {
        T res = 0;
        while (x) {
            res += sum[x];
            x -= lowbit(x);
        }
        return res;
    }
    T query(int L, int R) {
        return query(R) - query(L - 1);
    }
    void add(int x, T k) {
        while (x <= size) {
            sum[x] += k;
            x += lowbit(x);
        }
    }
}; // FenwickTree

非结构体

C++
int lowbit(const int x) {
    return x & -x;
}
const int N = 500005;
int n = N - 1, sum[N];
using B = int;
B query(int x) {
    B res = 0;
    while (x) {
        res += sum[x];
        x -= lowbit(x);
    }
    return res;
}
B query(int L, int R) {
    return query(R) - query(L - 1);
}
void add(int x, B k) {
    while (x <= n) {
        sum[x] += k;
        x += lowbit(x);
    }
}

结构体

C++
int lowbit(const int x) {
    return x & -x;
}
template<class T>
struct FenwickTree {
    vector<T> sum, sumX;
    int size;
    FenwickTree() {}
    FenwickTree(int n) {
        resize(n);
    }
    void resize(int n) {
        sum.resize(n + 1);
        sumX.resize(n + 1);
        size = n;
    }
    void clear() {
        sum.resize(0);
        sum.resize(size + 1);
        sumX.resize(0);
        sumX.resize(size + 1);
    }
    T query(int x) {
        T res = 0;
        for (int i = x ; i > 0 ; i -= lowbit(i)) {
            res += (x + 1) * sum[i] - sumX[i];
        }
        return res;
    }
    T query(int L, int R) {
        return query(R) - query(L - 1);
    }
    void add(int x, T k) {
        T kx = k * x;
        while (x <= size) {
            sum[x] += k;
            sumX[x] += kx;
            x += lowbit(x);
        }
    }
    void add(int L, int R, T k) {
        add(L, k);
        add(R + 1, -k);
    }
}; // FenwickTree

非结构体

C++
int lowbit(const int x) {
    return x & -x;
}
const int N = 1000005;
long long sum[N], sumX[N];
int n = N - 1;
using B = long long;
B query(int x) {
    B res = 0;
    for (int i = x ; i > 0 ; i -= lowbit(i)) {
        res += (x + 1) * sum[i] - sumX[i];
    }
    return res;
}
B query(int L, int R) {
    return query(R) - query(L - 1);
}
void add(int x, B k) {
    B kx = k * x;
    while (x <= n) {
        sum[x] += k;
        sumX[x] += kx;
        x += lowbit(x);
    }
}
void add(int L, int R, B k) {
    add(L, k);
    add(R + 1, -k);
}

单点修改-区间查询区间修改-区间查询

结构体

C++
int lowbit(const int x) {
    return x & -x;
}
template<class T>
struct FenwickTree {
    vector<vector<T>> sum;
    int sizeX, sizeY;
    FenwickTree() {}
    FenwickTree(int n, int m) {
        resize(n, m);
    }
    void resize(int n, int m) {
        sum.resize(n + 1);
        for (int i = 1 ; i <= n ; i++) {
            sum[i].resize(m + 1);
        }
        sizeX = n;
        sizeY = m;
    }
    void clear() {
        sum.resize(0);
        sum.resize(sizeX + 1);
        for (int i = 1 ; i <= sizeX ; i++) {
            sum[i].resize(sizeY + 1);
        }
    }
    T query(int x, int y) {
        T res = 0;
        for (int i = x ; i > 0 ; i -= lowbit(i)) {
            for (int j = y ; j > 0 ; j-= lowbit(j)) {
                res += sum[i][j];
            }
        }
        return res;
    }
    T query(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x2, y1 - 1) - query(x1 - 1, y2) + query(x1 - 1, y1 - 1);
    }
    void add(int x, int y, T k) {
        for (int i = x ; i <= sizeX ; i += lowbit(i)) {
            for (int j = y ; j <= sizeY ; j += lowbit(j)) {
                sum[i][j] += k;
            }
        }
    }
}; // FenwickTree

非结构体

C++
int lowbit(const int x) {
    return x & -x;
}
const int N = 5005, M = 5005;
int n = N - 1, m = M - 1;
using B = long long;
B sum[N][M];
B query(int x, int y) {
    B res = 0;
    for (int i = x ; i > 0 ; i -= lowbit(i)) {
        for (int j = y ; j > 0 ; j-= lowbit(j)) {
            res += sum[i][j];
        }
    }
    return res;
}
B query(int x1, int y1, int x2, int y2) {
    return query(x2, y2) - query(x2, y1 - 1) - query(x1 - 1, y2) + query(x1 - 1, y1 - 1);
}
void add(int x, int y, B k) {
    for (int i = x ; i <= n ; i += lowbit(i)) {
        for (int j = y ; j <= m ; j += lowbit(j)) {
            sum[i][j] += k;
        }
    }
}

结构体

C++
int lowbit(const int x) {
    return x & -x;
}
template<class T>
struct FenwickTree {
    vector<vector<T>> sum, sumX, sumY, sumXY;
    int sizeX, sizeY;
    FenwickTree() {}
    FenwickTree(int n, int m) {
        resize(n, m);
    }
    void resize(int n, int m) {
        sum.resize(n + 1);
        sumX.resize(n + 1);
        sumY.resize(n + 1);
        sumXY.resize(n + 1);
        for (int i = 1 ; i <= n ; i++) {
            sum[i].resize(m + 1);
            sumX[i].resize(m + 1);
            sumY[i].resize(m + 1);
            sumXY[i].resize(m + 1);
        }
        sizeX = n;
        sizeY = m;
    }
    void clear() {
        resize(0, 0);
        resize(sizeX, sizeY);
    }
    T query(int x, int y) {
        T res = 0;
        for (int i = x ; i > 0 ; i -= lowbit(i)) {
            for (int j = y ; j > 0 ; j-= lowbit(j)) {
                res += sum[i][j] * (x + 1) * (y + 1) - sumX[i][j] * (y + 1) - sumY[i][j] * (x + 1) + sumXY[i][j];
            }
        }
        return res;
    }
    T query(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x2, y1 - 1) - query(x1 - 1, y2) + query(x1 - 1, y1 - 1);
    }
    void add(int x, int y, T k) {
        T kx = k * x;
        T ky = k * y;
        T kxy = kx * y;
        for (int i = x ; i <= sizeX ; i += lowbit(i)) {
            for (int j = y ; j <= sizeY ; j += lowbit(j)) {
                sum[i][j] += k;
                sumX[i][j] += kx;
                sumY[i][j] += ky;
                sumXY[i][j] += kxy;
            }
        }
    }
    void add(int x1, int y1, int x2, int y2, T k) {
        add(x1, y1, k);
        add(x1, y2 + 1, -k);
        add(x2 + 1, y1, -k);
        add(x2 + 1, y2 + 1, k);
    }
}; // FenwickTree

非结构体

C++
int lowbit(const int x) {
    return x & -x;
}
const int N = 5005, M = 5005;
using B = long long;
B sum[N][M], sumX[N][M], sumY[N][M], sumXY[N][M];
int n = N - 1, m = M - 1;
B query(int x, int y) {
    B res = 0;
    for (int i = x ; i > 0 ; i -= lowbit(i)) {
        for (int j = y ; j > 0 ; j-= lowbit(j)) {
            res += sum[i][j] * (x + 1) * (y + 1) - sumX[i][j] * (y + 1) - sumY[i][j] * (x + 1) + sumXY[i][j];
        }
    }
    return res;
}
B query(int x1, int y1, int x2, int y2) {
    return query(x2, y2) - query(x2, y1 - 1) - query(x1 - 1, y2) + query(x1 - 1, y1 - 1);
}
void add(int x, int y, B k) {
    B kx = k * x;
    B ky = k * y;
    B kxy = kx * y;
    for (int i = x ; i <= n ; i += lowbit(i)) {
        for (int j = y ; j <= m ; j += lowbit(j)) {
            sum[i][j] += k;
            sumX[i][j] += kx;
            sumY[i][j] += ky;
            sumXY[i][j] += kxy;
        }
    }
}
void add(int x1, int y1, int x2, int y2, B k) {
    add(x1, y1, k);
    add(x1, y2 + 1, -k);
    add(x2 + 1, y1, -k);
    add(x2 + 1, y2 + 1, k);
}

C++
int lowbit(const int x) {
    return x & -x;
}
template<class T>
struct FenwickTree {
    vector<T> sum;
    int size;
    FenwickTree() {}
    FenwickTree(int n) {
        resize(n);
    }
    void resize(int n) {
        sum.resize(n + 1);
        size = n;
    }
    void clear() {
        sum.resize(0);
        sum.resize(size + 1);
    }
    T query(int x) {
        T res = 0;
        while (x) {
            res += sum[x];
            x -= lowbit(x);
        }
        return res;
    }
    T query(int L, int R) {
        return query(R) - query(L - 1);
    }
    void add(int x, T k) {
        while (x <= size) {
            sum[x] += k;
            x += lowbit(x);
        }
    }
    T kth(int rk) {
        int res = 0, now = 0;
        for (int i = 20 ; i >= 0 ; i--) {
            int k = 1 << i;
            if (now + k <= size && res + sum[now + k] < rk) {
                now += k;
                res += sum[now];
            }
        }
        return now + 1;
    }
}; // FenwickTree

例题

一维二维

洛谷P3374(单点修改区间查询)LOJ132(区间修改区间查询)

P3374 【模板】树状数组 1 - 洛谷

#132. 树状数组 3 ：区间修改，区间查询 - LibreOJ

LOJ133(单点修改区间查询)LOJ135(区间修改区间查询)

#133. 二维树状数组 1：单点修改，区间查询 - LibreOJ

#135. 二维树状数组 3：区间修改，区间查询 - LibreOJ

习题

洛谷P2163(二维数点)牛客76609F(按照排列循环/单点修改/求不同个数)蔚蓝系列赛 Round 2：原神主题赛蒙德D

P2163 [SHOI2007] 园丁的烦恼 - 洛谷

多次查询矩形中点的数量。

代码

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int lowbit(const int x) {
    return x & -x;
}
template<class T> struct FenwickTree {
    vector<T> sum;
    int size;
    FenwickTree() {}
    FenwickTree(const int n) {
        init(n);
    }
    void init(const int n) {
        size = n;
        sum.assign(n + 1, 0);
    }
    void clear() {
        sum.clear();
    }
    T query(int x) {
        T res = 0;
        while (x) {
            res += sum[x];
            x -= lowbit(x);
        }
        return res;
    }
    T query(const int L, const int R) {
        return query(R) - query(L - 1);
    }
    void add(int x, const T k) {
        while (x <= size) {
            sum[x] += k;
            x += lowbit(x);
        }
    }
}; // FenwickTree
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> idxX, idxY;
    vector<int> aX(n), aY(n), bX(m << 1), bY(m << 1);
    for (int i = 0 ; i < n ; i++) {
        cin >> aX[i] >> aY[i];
    }
    for (int i = 0 ; i < m ; i++) {
        cin >> bX[i] >> bY[i] >> bX[i + m] >> bY[i + m];
        bX[i]--;
        bY[i]--;
    }
    idxX.emplace_back(-100);
    idxY.emplace_back(-100);
    copy(make_move_iterator(begin(aX)), make_move_iterator(end(aX)), back_inserter(idxX));
    copy(make_move_iterator(begin(bX)), make_move_iterator(end(bX)), back_inserter(idxX));
    copy(make_move_iterator(begin(aY)), make_move_iterator(end(aY)), back_inserter(idxY));
    copy(make_move_iterator(begin(bY)), make_move_iterator(end(bY)), back_inserter(idxY));
    auto Unique = [&](auto& res) -> void {
        sort(begin(res), end(res));
        res.resize(unique(begin(res), end(res)) - begin(res));
    };
    auto get = [&](auto& res, int val) {
        return lower_bound(begin(res), end(res), val) - begin(res);
    };
    Unique(idxX);
    Unique(idxY);
    int lenX = idxX.size(), lenY = idxY.size();
    vector<int> X1[lenX], X2[lenX], X3[lenX], ans(m);
    for (int i = 0 ; i < n ; i++) {
        aX[i] = get(idxX, aX[i]);
        aY[i] = get(idxY, aY[i]);
        X1[aX[i]].emplace_back(i);
    }
    for (int i = 0 ; i < m ; i++) {
        bX[i] = get(idxX, bX[i]);
        bY[i] = get(idxY, bY[i]);
        bX[i + m] = get(idxX, bX[i + m]);
        bY[i + m] = get(idxY, bY[i + m]);
        X2[bX[i]].emplace_back(i);
        X3[bX[i + m]].emplace_back(i);
    }
    FenwickTree<int> ft(lenY);
    for (int i = 1 ; i < lenX ; i++) {
        for (auto& pos : X1[i]) {
            ft.add(aY[pos], 1);
        }
        for (auto& pos : X2[i]) {
            ans[pos] += ft.query(bY[pos]) - ft.query(bY[pos + m]);
        }
        for (auto& pos : X3[i]) {
            ans[pos] += ft.query(bY[pos + m]) - ft.query(bY[pos]);
        }
    }
    for (int i = 0 ; i < m ; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

F-小红的好子串询问_牛客周赛 Round 36

一个串(只包含r,e,d)

好串为按照排列循环\(\{red,rde,erd,edr,der,dre\}\)

操作\(1\),第 \(x\) 个字符修改为 \(ch\)。

操作\(2\),查询区间 \([L,R]\) 修改多少个字符可以变为好串。

代码

C++
#include <bits/stdc++.h>
using namespace std;
// 2024 OneWan
const int N = 100005;
int lowbit(int x) {
    return x & -x;
}
int sum[6][N];
int n;
void add(int idx, int x, int k) {
    while (x <= n) {
        sum[idx][x] += k;
        x += lowbit(x);
    }
}
int query(int idx, int x) {
    int res = 0;
    while (x) {
        res += sum[idx][x];
        x -= lowbit(x);
    }
    return res;
}
string s[] = {
    "red", "rde",
    "erd", "edr",
    "der", "dre"
};
string str;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int q;
    cin >> n >> q;
    cin >> str;
    str = " " + str;
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 0 ; j < 6 ; j++) {
            if (s[j][(i - 1) % 3] != str[i]) {
                add(j, i, 1);
            }
        }
    }
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            char ch;
            cin >> x >> ch;
            for (int j = 0 ; j < 6 ; j++) {
                if (s[j][(x - 1) % 3] != str[x]) {
                    add(j, x, -1);
                }
            }
            str[x] = ch;
            for (int j = 0 ; j < 6 ; j++) {
                if (s[j][(x - 1) % 3] != str[x]) {
                    add(j, x, 1);
                }
            }
        } else {
            int L, R;
            cin >> L >> R;
            int ans = 0x7fffffff;
            for (int j = 0 ; j < 6 ; j++) {
                ans = min(ans, query(j, R) - query(j, L - 1));
            }
            cout << ans << "\n";
        }
    }
    return 0;
}

可以知道对于每个数, 都有一个对应的区间 \(L\in [pos_{x,i - 1}+1,pos_{x,i}],R\in[pos_{x,i+x-1},pos_{x,i+x}-1]\)

我们通过枚举左端点 \(L\), 使用差分树状数组来维护 \(R\), 即可求解

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int a[1000005];
vector<int> pos[1000005];
i64 sum[1000005];
int lowbit(int x) {
    return x & -x;
}
void add(int x, i64 k) {
    while (x <= 1000000) {
        sum[x] += k;
        x += lowbit(x);
    }
}
i64 query(int x) {
    i64 res = 0;
    while (x) {
        res += sum[x];
        x -= lowbit(x);
    }
    return res;
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    vector<array<int, 4>> qu;
    for (int i = 1 ; i <= m ; i++) {
        int L, R;
        cin >> L >> R;
        qu.push_back({L, R, i, 0});
    }
    for (int x = 1 ; x <= n ; x++) {
        for (int i = 0 ; i + x - 1 < (int) pos[x].size() ; i++) {
            // L in [pos[i - 1] + 1, pos[i]]
            // R in [pos[i + x - 1], pos[i + x] - 1]
            int L1 = 0;
            if (i - 1 >= 0) {
                L1 = pos[x][i - 1] + 1;
            }
            int R1 = pos[x][i];
            int L2 = pos[x][i + x - 1];
            int R2 = n + 1;
            if (i + x < (int) pos[x].size()) {
                R2 = pos[x][i + x] - 1;
            }
            qu.push_back({L1, L2, 0, x});
            qu.push_back({L1, R2 + 1, 0, -x});
            qu.push_back({R1 + 1, L2, 0, -x});
            qu.push_back({R1 + 1, R2 + 1, 0, x});
        }
    }
    sort(begin(qu), end(qu));
    vector<i64> ans(m + 1);
    for (auto &[L, R, idx, val] : qu) {
        if (idx == 0) {
            add(R, val);
        } else {
            ans[idx] = query(R);
        }
    }
    for (int i = 1 ; i <= m ; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}