点加算長方形和(Point Add Rectangle Sum)
(datastructure/point_add_rectangle_sum.cpp)

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

説明

点追加と長方形和クエリをまとめて処理する。 全追加点を先に集めて、座圧済み 2 次元 BIT を offline 構築する。

できること

• PointAddRectangleSum<T> solver 空の solver を作る
• void add_point(int x, int y, T w) 点 (x, y) に重み w を追加する操作を積む
• void add_query(int l, int d, int r, int u) 半開長方形 [l, r) x [d, u) の和クエリを積む
• vector<T> solve() 追加順に各クエリの答えを返す

使い方

初期点も更新点も add_point で順に積む。 solve() はそれまでに現れる全追加点の座標から 2 次元 BIT を構築し、操作列を先頭から再生する。

Depends on

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

Verified with

• test/yosupo_point_add_rectangle_sum.test.cpp

Code

using namespace std;

#include "binaryindexedtree.cpp"

template<class T>
struct PointAddRectangleSum {
    struct Operation {
        int type;
        int x, y, z;
        T w;
    };

    vector<Operation> ops;
    vector<int> xs;

    void add_point(int x, int y, T w) {
        ops.push_back({0, x, y, 0, w});
        xs.push_back(x);
    }

    void add_query(int l, int d, int r, int u) {
        ops.push_back({1, l, d, r, u});
    }

    vector<T> solve() const {
        vector<int> ord_x = xs;
        sort(ord_x.begin(), ord_x.end());
        ord_x.erase(unique(ord_x.begin(), ord_x.end()), ord_x.end());

        int m = (int)ord_x.size();
        vector<vector<int>> ys(m + 1);
        for (auto op : ops) {
            if (op.type != 0) continue;
            int xi = (int)(lower_bound(ord_x.begin(), ord_x.end(), op.x) - ord_x.begin()) + 1;
            for (int x = xi; x <= m; x += x & -x) ys[x].push_back(op.y);
        }
        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());
        }

        vector<BIT<T>> bit;
        bit.reserve(m + 1);
        bit.emplace_back(0);
        for (int i = 1; i <= m; ++i) bit.emplace_back((int)ys[i].size());

        auto add = [&](int x, int y, T w) {
            int xi = (int)(lower_bound(ord_x.begin(), ord_x.end(), x) - ord_x.begin()) + 1;
            for (int i = xi; i <= m; i += i & -i) {
                int yi = (int)(lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin());
                bit[i].add(yi, w);
            }
        };
        auto sum = [&](int x, int y) {
            T ret = 0;
            int xi = (int)(lower_bound(ord_x.begin(), ord_x.end(), x) - ord_x.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;
        };

        vector<T> ans;
        for (auto op : ops) {
            if (op.type == 0) {
                add(op.x, op.y, (T)op.w);
            } else {
                ans.push_back(sum(op.z, op.w) - sum(op.z, op.y) - sum(op.x, op.w) + sum(op.x, op.y));
            }
        }
        return ans;
    }
};

/**
 * @brief 点加算長方形和(Point Add Rectangle Sum)
 */

#line 1 "datastructure/point_add_rectangle_sum.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/point_add_rectangle_sum.cpp"

template<class T>
struct PointAddRectangleSum {
    struct Operation {
        int type;
        int x, y, z;
        T w;
    };

    vector<Operation> ops;
    vector<int> xs;

    void add_point(int x, int y, T w) {
        ops.push_back({0, x, y, 0, w});
        xs.push_back(x);
    }

    void add_query(int l, int d, int r, int u) {
        ops.push_back({1, l, d, r, u});
    }

    vector<T> solve() const {
        vector<int> ord_x = xs;
        sort(ord_x.begin(), ord_x.end());
        ord_x.erase(unique(ord_x.begin(), ord_x.end()), ord_x.end());

        int m = (int)ord_x.size();
        vector<vector<int>> ys(m + 1);
        for (auto op : ops) {
            if (op.type != 0) continue;
            int xi = (int)(lower_bound(ord_x.begin(), ord_x.end(), op.x) - ord_x.begin()) + 1;
            for (int x = xi; x <= m; x += x & -x) ys[x].push_back(op.y);
        }
        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());
        }

        vector<BIT<T>> bit;
        bit.reserve(m + 1);
        bit.emplace_back(0);
        for (int i = 1; i <= m; ++i) bit.emplace_back((int)ys[i].size());

        auto add = [&](int x, int y, T w) {
            int xi = (int)(lower_bound(ord_x.begin(), ord_x.end(), x) - ord_x.begin()) + 1;
            for (int i = xi; i <= m; i += i & -i) {
                int yi = (int)(lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin());
                bit[i].add(yi, w);
            }
        };
        auto sum = [&](int x, int y) {
            T ret = 0;
            int xi = (int)(lower_bound(ord_x.begin(), ord_x.end(), x) - ord_x.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;
        };

        vector<T> ans;
        for (auto op : ops) {
            if (op.type == 0) {
                add(op.x, op.y, (T)op.w);
            } else {
                ans.push_back(sum(op.z, op.w) - sum(op.z, op.y) - sum(op.x, op.w) + sum(op.x, op.y));
            }
        }
        return ans;
    }
};

/**
 * @brief 点加算長方形和(Point Add Rectangle Sum)
 */

Back to top page