data_structure/rectangle_sum.hpp

• View this file on GitHub
• Last update: 2024-03-29 10:57:45+09:00
• Include: #include "data_structure/rectangle_sum.hpp"

Depends on

• data_structure/fenwick_tree.hpp
• data_structure/operations.hpp

Verified with

• data_structure/test/rectangle_sum.test.cpp

Code

#pragma once
#include "fenwick_tree.hpp"
#include <algorithm>
template <typename C, typename V>
class RectangleSum {
    struct Point {
        C x, y;
        V v;
    };
    struct Query {
        C xl, xr, yl, yr;
        int idx;
    };
    std::vector<Point> pts;
    std::vector<Query> qrs;
public:
    RectangleSum() : pts(), qrs() {}
    void add_point(C x, C y, V v) {
        pts.emplace_back(Point{x, y, v});
    }
    void add_query(C xl, C xr, C yl, C yr) {
        qrs.emplace_back(Query{xl, xr, yl, yr, (int)qrs.size()});
    }
    std::vector<V> solve() {
        std::sort(pts.begin(), pts.end(), [](const Point &p0, const Point &p1) -> bool {
            return p0.x < p1.x;
        });
        struct Q {
            C x, d, u;
            int id;
            bool is_positive;
        };
        std::vector<Q> q_;
        q_.reserve(2 * qrs.size());
        for (const Query &qr : qrs) {
            q_.push_back(Q{qr.xl, qr.yl, qr.yr, qr.idx, false});
            q_.push_back(Q{qr.xr, qr.yl, qr.yr, qr.idx, true});
        }
        std::sort(q_.begin(), q_.end(), [](const Q &q0, const Q &q1) -> bool {
            return q0.x < q1.x;
        });
        std::vector<C> ys;
        ys.reserve(pts.size());
        for (const Point &p : pts) {
            ys.push_back(p.y);
        }
        std::sort(ys.begin(), ys.end());
        ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
        FenwickTreeAdd<V> fw((int)ys.size());
        std::vector<V> ret(qrs.size(), 0);
        typename std::vector<Point>::iterator it = pts.begin();
        for (const Q &q : q_) {
            while (it != pts.end() && it->x < q.x) {
                int y = (int)(std::lower_bound(ys.begin(), ys.end(), it->y) - ys.begin());
                fw.add(y, it->v);
                ++it;
            }
            int d = (int)(std::lower_bound(ys.begin(), ys.end(), q.d) - ys.begin());
            int u = (int)(std::lower_bound(ys.begin(), ys.end(), q.u) - ys.begin());
            V sum = fw.sum(d, u);
            if (q.is_positive) {
                ret[q.id] += sum;
            } else {
                ret[q.id] -= sum;
            }
        }
        return ret;
    }
};

#line 2 "data_structure/fenwick_tree.hpp"

#include <cassert>
#include <vector>
#line 2 "data_structure/operations.hpp"

#include <algorithm>
#include <limits>
#include <utility>

template <typename T>
struct Add {
    using Value = T;
    static Value id() { return T(0); }
    static Value op(const Value &lhs, const Value &rhs) { return lhs + rhs; }
    static Value inv(const Value &x) { return -x; }
};

template <typename T>
struct Mul {
    using Value = T;
    static Value id() { return Value(1); }
    static Value op(const Value &lhs, const Value &rhs) { return lhs * rhs; }
    static Value inv(const Value &x) { return Value(1) / x; }
};

template <typename T>
struct Min {
    static_assert(std::numeric_limits<T>::is_specialized);
    using Value = T;
    static Value id() { return std::numeric_limits<T>::max(); }
    static Value op(const Value &lhs, const Value &rhs) {
        return std::min(lhs, rhs);
    }
};

template <typename T>
struct Max {
    static_assert(std::numeric_limits<T>::is_specialized);
    using Value = T;
    static Value id() { return std::numeric_limits<Value>::min(); }
    static Value op(const Value &lhs, const Value &rhs) {
        return std::max(lhs, rhs);
    }
};

template <typename T>
struct Xor {
    using Value = T;
    static Value id() { return T(0); }
    static Value op(const Value &lhs, const Value &rhs) { return lhs ^ rhs; }
    static Value inv(const Value &x) { return x; }
};

template <typename Monoid>
struct Reversible {
    using Value = std::pair<typename Monoid::Value, typename Monoid::Value>;
    static Value id() { return Value(Monoid::id(), Monoid::id()); }
    static Value op(const Value &v1, const Value &v2) {
        return Value(Monoid::op(v1.first, v2.first),
                     Monoid::op(v2.second, v1.second));
    }
};
#line 6 "data_structure/fenwick_tree.hpp"

template <typename CommutativeGroup>
class FenwickTree {
public:
    using Value = typename CommutativeGroup::Value;

private:
    std::vector<Value> data;

public:
    FenwickTree(int n) : data(n, CommutativeGroup::id()) {}

    void add(int idx, const Value &x) {
        assert(idx >= 0 && idx < (int)data.size());
        for (; idx < (int)data.size(); idx |= idx + 1) {
            data[idx] = CommutativeGroup::op(data[idx], x);
        }
    }

    Value sum(int r) const {
        assert(r >= 0 && r <= (int)data.size());
        Value ret = CommutativeGroup::id();
        for (; r > 0; r &= r - 1) {
            ret = CommutativeGroup::op(ret, data[r - 1]);
        }
        return ret;
    }

    Value sum(int l, int r) const {
        assert(l >= 0 && l <= r && r <= (int)data.size());
        return CommutativeGroup::op(sum(r), CommutativeGroup::inv(sum(l)));
    }
};

template <typename T>
using FenwickTreeAdd = FenwickTree<Add<T>>;
#line 4 "data_structure/rectangle_sum.hpp"
template <typename C, typename V>
class RectangleSum {
    struct Point {
        C x, y;
        V v;
    };
    struct Query {
        C xl, xr, yl, yr;
        int idx;
    };
    std::vector<Point> pts;
    std::vector<Query> qrs;
public:
    RectangleSum() : pts(), qrs() {}
    void add_point(C x, C y, V v) {
        pts.emplace_back(Point{x, y, v});
    }
    void add_query(C xl, C xr, C yl, C yr) {
        qrs.emplace_back(Query{xl, xr, yl, yr, (int)qrs.size()});
    }
    std::vector<V> solve() {
        std::sort(pts.begin(), pts.end(), [](const Point &p0, const Point &p1) -> bool {
            return p0.x < p1.x;
        });
        struct Q {
            C x, d, u;
            int id;
            bool is_positive;
        };
        std::vector<Q> q_;
        q_.reserve(2 * qrs.size());
        for (const Query &qr : qrs) {
            q_.push_back(Q{qr.xl, qr.yl, qr.yr, qr.idx, false});
            q_.push_back(Q{qr.xr, qr.yl, qr.yr, qr.idx, true});
        }
        std::sort(q_.begin(), q_.end(), [](const Q &q0, const Q &q1) -> bool {
            return q0.x < q1.x;
        });
        std::vector<C> ys;
        ys.reserve(pts.size());
        for (const Point &p : pts) {
            ys.push_back(p.y);
        }
        std::sort(ys.begin(), ys.end());
        ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
        FenwickTreeAdd<V> fw((int)ys.size());
        std::vector<V> ret(qrs.size(), 0);
        typename std::vector<Point>::iterator it = pts.begin();
        for (const Q &q : q_) {
            while (it != pts.end() && it->x < q.x) {
                int y = (int)(std::lower_bound(ys.begin(), ys.end(), it->y) - ys.begin());
                fw.add(y, it->v);
                ++it;
            }
            int d = (int)(std::lower_bound(ys.begin(), ys.end(), q.d) - ys.begin());
            int u = (int)(std::lower_bound(ys.begin(), ys.end(), q.u) - ys.begin());
            V sum = fw.sum(d, u);
            if (q.is_positive) {
                ret[q.id] += sum;
            } else {
                ret[q.id] -= sum;
            }
        }
        return ret;
    }
};

Back to top page