2次元Fenwick Tree(2D BIT)
(datastructure/fenwick_tree_2d.cpp)

• View this file on GitHub
• Last update: 2026-03-12 00:49:33+09:00

説明

更新される点集合を先に登録してから構築する座圧 2 次元 BIT。 点加算と半開長方形和を各 $O(log^2 N)$ で扱う。

できること

• FenwickTree2D<T> fw 空の 2 次元 BIT を作る
• void add_point(int x, int y) 今後更新する可能性がある点 (x, y) を登録する
• void build() 登録済みの点から内部座圧を構築する
• void add(int x, int y, T w) 登録済みの点 (x, y) に w を加える。未登録点は使えない
• T sum(int x, int y) 半開長方形 (-inf, x) x (-inf, y) の総和を返す
• T sum(int l, int d, int r, int u) 半開長方形 [l, r) x [d, u) の総和を返す

使い方

更新に使う全点を add_point で登録してから build() する。 build() 後は add と sum を任意順に呼べる。

Depends on

• Binary Indexed Tree(BIT) (datastructure/binaryindexedtree.cpp)

Verified with

• test/yosupo_point_add_rectangle_sum_fenwick_tree_2d.test.cpp

Code

using namespace std;

#include "binaryindexedtree.cpp"

template<class T>
struct FenwickTree2D {
    vector<pair<int, int>> points;
    vector<int> xs;
    vector<vector<int>> ys;
    vector<BIT<T>> bit;
    bool built = false;

    void add_point(int x, int y) {
        assert(!built);
        points.push_back({x, y});
        xs.push_back(x);
    }

    void build() {
        assert(!built);
        built = true;

        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());

        vector<pair<int, int>> ord = points;
        sort(ord.begin(), ord.end());
        ord.erase(unique(ord.begin(), ord.end()), ord.end());

        int m = (int)xs.size();
        ys.assign(m + 1, {});
        for (auto [x, y] : ord) {
            int xi = (int)(lower_bound(xs.begin(), xs.end(), x) - xs.begin()) + 1;
            for (int i = xi; i <= m; i += i & -i) ys[i].push_back(y);
        }
        bit.clear();
        bit.reserve(m + 1);
        bit.emplace_back(0);
        for (int i = 1; i <= m; ++i) {
            sort(ys[i].begin(), ys[i].end());
            ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
            bit.emplace_back((int)ys[i].size());
        }
    }

    void add(int x, int y, T w) {
        assert(built);
        int m = (int)xs.size();
        int xi = (int)(lower_bound(xs.begin(), xs.end(), x) - xs.begin());
        assert(xi < m && xs[xi] == x);
        ++xi;
        for (int i = xi; i <= m; i += i & -i) {
            int yi = (int)(lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin());
            assert(yi < (int)ys[i].size() && ys[i][yi] == y);
            bit[i].add(yi, w);
        }
    }

    T sum(int x, int y) {
        assert(built);
        T ret = 0;
        int xi = (int)(lower_bound(xs.begin(), xs.end(), x) - xs.begin());
        for (int i = xi; i > 0; i -= i & -i) {
            int yi = (int)(lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin());
            ret += bit[i].sum(yi);
        }
        return ret;
    }

    T sum(int l, int d, int r, int u) {
        return sum(r, u) - sum(r, d) - sum(l, u) + sum(l, d);
    }
};

/**
 * @brief 2次元Fenwick Tree(2D BIT)
 */

#line 1 "datastructure/fenwick_tree_2d.cpp"
using namespace std;

#line 1 "datastructure/binaryindexedtree.cpp"
template<class T>
class BIT {
    vector<T> bit;
    int m, n;
public:
    BIT(int n): bit(n), m(1), n(n) {
        while (m < n) m <<= 1;
    }

    T sum(int k){
        T ret = 0;
        for (; k > 0; k -= (k & -k)) ret += bit[k - 1];
        return ret;
    }

    void add(int k, T x){
        for (k++; k <= n; k += (k & -k)) bit[k - 1] += x;
    }

    int lower_bound(T x) {
        if (x <= 0) return 0;
        int i = 0;
        for (int j = m; j; j >>= 1) {
            if (i + j <= n && bit[i + j - 1] < x) x -= bit[i + j - 1], i += j;
        }
        return min(i + 1, n);
    }
};

/**
 * @brief Binary Indexed Tree(BIT)
 */
#line 4 "datastructure/fenwick_tree_2d.cpp"

template<class T>
struct FenwickTree2D {
    vector<pair<int, int>> points;
    vector<int> xs;
    vector<vector<int>> ys;
    vector<BIT<T>> bit;
    bool built = false;

    void add_point(int x, int y) {
        assert(!built);
        points.push_back({x, y});
        xs.push_back(x);
    }

    void build() {
        assert(!built);
        built = true;

        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());

        vector<pair<int, int>> ord = points;
        sort(ord.begin(), ord.end());
        ord.erase(unique(ord.begin(), ord.end()), ord.end());

        int m = (int)xs.size();
        ys.assign(m + 1, {});
        for (auto [x, y] : ord) {
            int xi = (int)(lower_bound(xs.begin(), xs.end(), x) - xs.begin()) + 1;
            for (int i = xi; i <= m; i += i & -i) ys[i].push_back(y);
        }
        bit.clear();
        bit.reserve(m + 1);
        bit.emplace_back(0);
        for (int i = 1; i <= m; ++i) {
            sort(ys[i].begin(), ys[i].end());
            ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
            bit.emplace_back((int)ys[i].size());
        }
    }

    void add(int x, int y, T w) {
        assert(built);
        int m = (int)xs.size();
        int xi = (int)(lower_bound(xs.begin(), xs.end(), x) - xs.begin());
        assert(xi < m && xs[xi] == x);
        ++xi;
        for (int i = xi; i <= m; i += i & -i) {
            int yi = (int)(lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin());
            assert(yi < (int)ys[i].size() && ys[i][yi] == y);
            bit[i].add(yi, w);
        }
    }

    T sum(int x, int y) {
        assert(built);
        T ret = 0;
        int xi = (int)(lower_bound(xs.begin(), xs.end(), x) - xs.begin());
        for (int i = xi; i > 0; i -= i & -i) {
            int yi = (int)(lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin());
            ret += bit[i].sum(yi);
        }
        return ret;
    }

    T sum(int l, int d, int r, int u) {
        return sum(r, u) - sum(r, d) - sum(l, u) + sum(l, d);
    }
};

/**
 * @brief 2次元Fenwick Tree(2D BIT)
 */

Back to top page