静的長方形和(Static Rectangle Sum)
(datastructure/static_rectangle_sum.cpp)

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

説明

静的な重み付き点集合に対して、長方形内の重み和をまとめて処理する。 x 方向の sweep と y 上の BIT を使う。

できること

• StaticRectangleSum<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() 追加順に各クエリの重み和を返す

使い方

先に点とクエリを全部追加してから solve() を呼ぶ。 y 座標は内部で座圧し、各クエリを x < r と x < l の差に分解して処理する。

Depends on

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

Verified with

• test/yosupo_static_rectangle_sum.test.cpp

Code

using namespace std;

#include "binaryindexedtree.cpp"

template<class T>
struct StaticRectangleSum {
    struct Point {
        int x, y;
        T w;
    };

    struct Event {
        int x, d, u, id, sign;

        bool operator<(const Event& other) const {
            return x < other.x;
        }
    };

    vector<Point> points;
    vector<Event> events;
    vector<int> ys;

    void add_point(int x, int y, T w) {
        points.push_back({x, y, w});
        ys.push_back(y);
    }

    void add_query(int l, int d, int r, int u) {
        int id = (int)events.size() / 2;
        events.push_back({r, d, u, id, 1});
        events.push_back({l, d, u, id, -1});
        ys.push_back(d);
        ys.push_back(u);
    }

    vector<T> solve() {
        vector<int> ord_y = ys;
        sort(ord_y.begin(), ord_y.end());
        ord_y.erase(unique(ord_y.begin(), ord_y.end()), ord_y.end());

        auto get_y = [&](int y) {
            return (int)(lower_bound(ord_y.begin(), ord_y.end(), y) - ord_y.begin());
        };

        vector<Point> ps = points;
        for (auto& p : ps) p.y = get_y(p.y);
        for (auto& e : events) {
            e.d = get_y(e.d);
            e.u = get_y(e.u);
        }

        sort(ps.begin(), ps.end(), [](const Point& a, const Point& b) {
            return a.x < b.x;
        });
        sort(events.begin(), events.end());

        int q = (int)events.size() / 2;
        vector<T> ans(q, 0);
        BIT<T> bit((int)ord_y.size());
        int i = 0;
        for (auto e : events) {
            while (i < (int)ps.size() && ps[i].x < e.x) {
                bit.add(ps[i].y, ps[i].w);
                ++i;
            }
            ans[e.id] += (bit.sum(e.u) - bit.sum(e.d)) * e.sign;
        }
        return ans;
    }
};

/**
 * @brief 静的長方形和(Static Rectangle Sum)
 */

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

template<class T>
struct StaticRectangleSum {
    struct Point {
        int x, y;
        T w;
    };

    struct Event {
        int x, d, u, id, sign;

        bool operator<(const Event& other) const {
            return x < other.x;
        }
    };

    vector<Point> points;
    vector<Event> events;
    vector<int> ys;

    void add_point(int x, int y, T w) {
        points.push_back({x, y, w});
        ys.push_back(y);
    }

    void add_query(int l, int d, int r, int u) {
        int id = (int)events.size() / 2;
        events.push_back({r, d, u, id, 1});
        events.push_back({l, d, u, id, -1});
        ys.push_back(d);
        ys.push_back(u);
    }

    vector<T> solve() {
        vector<int> ord_y = ys;
        sort(ord_y.begin(), ord_y.end());
        ord_y.erase(unique(ord_y.begin(), ord_y.end()), ord_y.end());

        auto get_y = [&](int y) {
            return (int)(lower_bound(ord_y.begin(), ord_y.end(), y) - ord_y.begin());
        };

        vector<Point> ps = points;
        for (auto& p : ps) p.y = get_y(p.y);
        for (auto& e : events) {
            e.d = get_y(e.d);
            e.u = get_y(e.u);
        }

        sort(ps.begin(), ps.end(), [](const Point& a, const Point& b) {
            return a.x < b.x;
        });
        sort(events.begin(), events.end());

        int q = (int)events.size() / 2;
        vector<T> ans(q, 0);
        BIT<T> bit((int)ord_y.size());
        int i = 0;
        for (auto e : events) {
            while (i < (int)ps.size() && ps[i].x < e.x) {
                bit.add(ps[i].y, ps[i].w);
                ++i;
            }
            ans[e.id] += (bit.sum(e.u) - bit.sum(e.d)) * e.sign;
        }
        return ans;
    }
};

/**
 * @brief 静的長方形和(Static Rectangle Sum)
 */

Back to top page