Offline Rectangle Add Rectangle Sum
(ds/range_query/offline_rectangle_add_rectangle_sum.hpp)

View this file on GitHub
Last update: 2026-07-16 21:06:02+09:00
Include: #include "ds/range_query/offline_rectangle_add_rectangle_sum.hpp"

Overview

m1une::ds::OfflineRectangleAddRectangleSum<T, X, Y> records additions to axis-aligned rectangles and rectangle-sum queries, then evaluates the complete batch with an offline sweep.

Every rectangle is half-open:

\[[x_l,x_r)\times[y_l,y_r).\]

An update adds value to every unit cell in its rectangle. A query returns the sum of all cells in its rectangle. Equivalently, the structure computes the area-weighted integral of the piecewise-constant rectangle additions. Integer coordinates therefore match the usual grid interpretation exactly.

All recorded updates affect every recorded query. Insertion order is not a time axis. Query IDs and returned answers use query insertion order, and repeated calls to calculate() do not mutate the batch.

Requirements

template <class T, class X = long long, class Y = X>
class OfflineRectangleAddRectangleSum;

X and Y must be strictly ordered by <.
T{} must be zero. T must support copying, +=, -=, addition, subtraction, and multiplication.
Coordinates must be explicitly constructible as T. Coordinate products are performed after conversion to T, which is useful for modular arithmetic.
Exact arithmetic results must fit in T, unless T intentionally implements modular arithmetic.

Interface

using value_type = T;
using x_type = X;
using y_type = Y;

int update_count() const;
int query_count() const;
bool empty() const;

void reserve_updates(int capacity);
void reserve_queries(int capacity);
void clear();

int add_rectangle(
    const X& x_lower,
    const X& x_upper,
    const Y& y_lower,
    const Y& y_upper,
    const T& value
);

int add_query(
    const X& x_lower,
    const X& x_upper,
    const Y& y_lower,
    const Y& y_upper
);

std::vector<T> calculate() const;

Operations

Method	Description	Complexity
Default construction	Creates an empty batch.	$O(1)$
`update_count()`	Returns the number of recorded rectangle additions.	$O(1)$
`query_count()`	Returns the number of recorded sum queries.	$O(1)$
`empty()`	Returns whether both logs are empty.	$O(1)$
`reserve_updates(capacity)`	Reserves update storage.	$O(N)$ worst case
`reserve_queries(capacity)`	Reserves query storage.	$O(Q)$ worst case
`clear()`	Removes every update and query while preserving allocated capacity.	$O(N+Q)$
`add_rectangle(xl, xr, yl, yr, value)`	Records an addition and returns its insertion-order update ID. Empty rectangles are allowed.	Amortized $O(1)$
`add_query(xl, xr, yl, yr)`	Records a sum query and returns its insertion-order query ID. Empty rectangles are allowed.	Amortized $O(1)$
`calculate()`	Returns all answers in query insertion order without mutating the object.	$O((N+Q)\log(N+Q))$ time and $O(N+Q)$ memory

Here $N$ is the number of updates and $Q$ is the number of queries. Invalid rectangles with a lower boundary greater than the corresponding upper boundary trigger an assertion.

The implementation converts every rectangle addition into four weighted corner events. A sweep over x and a Fenwick tree over compressed y-coordinates evaluate the two-dimensional prefix sums used by inclusion-exclusion.

Example

#include "ds/range_query/offline_rectangle_add_rectangle_sum.hpp"

#include <cassert>

int main() {
    m1une::ds::OfflineRectangleAddRectangleSum<long long> offline;

    offline.add_rectangle(0, 3, 0, 2, 5);
    int query_id = offline.add_query(1, 4, 1, 3);

    const auto answers = offline.calculate();
    assert(answers[query_id] == 10);
}

Depends on

Fenwick Tree (Binary Indexed Tree) (ds/range_query/fenwick_tree.hpp)

Verified with

verify/ds/range_query/offline_rectangle_add_rectangle_sum.test.cpp

Code

#ifndef M1UNE_OFFLINE_RECTANGLE_ADD_RECTANGLE_SUM_HPP
#define M1UNE_OFFLINE_RECTANGLE_ADD_RECTANGLE_SUM_HPP 1

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

#include "fenwick_tree.hpp"

namespace m1une {
namespace ds {

// Records rectangle additions and rectangle-sum queries, then evaluates the
// complete static batch with an offline sweep.
template <class T, class X = long long, class Y = X>
class OfflineRectangleAddRectangleSum {
   public:
    using value_type = T;
    using x_type = X;
    using y_type = Y;

   private:
    struct Update {
        X x_lower;
        X x_upper;
        Y y_lower;
        Y y_upper;
        T value;
    };

    struct Query {
        X x_lower;
        X x_upper;
        Y y_lower;
        Y y_upper;
    };

    struct Coefficient {
        T xy{};
        T x{};
        T y{};
        T constant{};

        Coefficient& operator+=(const Coefficient& other) {
            xy += other.xy;
            x += other.x;
            y += other.y;
            constant += other.constant;
            return *this;
        }
    };

    struct PointEvent {
        X x;
        Y y;
        Coefficient coefficient;
    };

    struct PrefixEvent {
        X x;
        Y y;
        int query_id;
        bool subtract;
    };

    std::vector<Update> _updates;
    std::vector<Query> _queries;

    template <class Coordinate>
    static bool equivalent(const Coordinate& first, const Coordinate& second) {
        return !(first < second) && !(second < first);
    }

    static Coefficient make_coefficient(
        const X& x,
        const Y& y,
        const T& signed_value
    ) {
        const T converted_x(x);
        const T converted_y(y);
        return {
            signed_value,
            T{} - signed_value * converted_y,
            T{} - signed_value * converted_x,
            signed_value * converted_x * converted_y
        };
    }

    static T evaluate(
        const Coefficient& coefficient,
        const X& x,
        const Y& y
    ) {
        const T converted_x(x);
        const T converted_y(y);
        return coefficient.xy * converted_x * converted_y +
               coefficient.x * converted_x +
               coefficient.y * converted_y +
               coefficient.constant;
    }

   public:
    int update_count() const {
        return int(_updates.size());
    }

    int query_count() const {
        return int(_queries.size());
    }

    bool empty() const {
        return _updates.empty() && _queries.empty();
    }

    void reserve_updates(int capacity) {
        assert(0 <= capacity);
        _updates.reserve(capacity);
    }

    void reserve_queries(int capacity) {
        assert(0 <= capacity);
        _queries.reserve(capacity);
    }

    void clear() {
        _updates.clear();
        _queries.clear();
    }

    int add_rectangle(
        const X& x_lower,
        const X& x_upper,
        const Y& y_lower,
        const Y& y_upper,
        const T& value
    ) {
        assert(!(x_upper < x_lower));
        assert(!(y_upper < y_lower));
        const int id = update_count();
        _updates.push_back(Update{x_lower, x_upper, y_lower, y_upper, value});
        return id;
    }

    int add_query(
        const X& x_lower,
        const X& x_upper,
        const Y& y_lower,
        const Y& y_upper
    ) {
        assert(!(x_upper < x_lower));
        assert(!(y_upper < y_lower));
        const int id = query_count();
        _queries.push_back(Query{x_lower, x_upper, y_lower, y_upper});
        return id;
    }

    std::vector<T> calculate() const {
        std::vector<T> answers(_queries.size(), T{});
        if (_queries.empty() || _updates.empty()) return answers;

        std::vector<PointEvent> point_events;
        point_events.reserve(4 * _updates.size());
        std::vector<Y> y_coordinates;
        y_coordinates.reserve(2 * _updates.size());
        for (const Update& update : _updates) {
            if (equivalent(update.x_lower, update.x_upper) ||
                equivalent(update.y_lower, update.y_upper)) {
                continue;
            }
            const T negative_value = T{} - update.value;
            point_events.push_back(PointEvent{
                update.x_lower,
                update.y_lower,
                make_coefficient(update.x_lower, update.y_lower, update.value)
            });
            point_events.push_back(PointEvent{
                update.x_lower,
                update.y_upper,
                make_coefficient(update.x_lower, update.y_upper, negative_value)
            });
            point_events.push_back(PointEvent{
                update.x_upper,
                update.y_lower,
                make_coefficient(update.x_upper, update.y_lower, negative_value)
            });
            point_events.push_back(PointEvent{
                update.x_upper,
                update.y_upper,
                make_coefficient(update.x_upper, update.y_upper, update.value)
            });
            y_coordinates.push_back(update.y_lower);
            y_coordinates.push_back(update.y_upper);
        }
        if (point_events.empty()) return answers;

        std::sort(y_coordinates.begin(), y_coordinates.end());
        y_coordinates.erase(
            std::unique(
                y_coordinates.begin(),
                y_coordinates.end(),
                [](const Y& first, const Y& second) {
                    return equivalent(first, second);
                }
            ),
            y_coordinates.end()
        );
        std::sort(
            point_events.begin(),
            point_events.end(),
            [](const PointEvent& first, const PointEvent& second) {
                return first.x < second.x;
            }
        );

        std::vector<PrefixEvent> prefix_events;
        prefix_events.reserve(4 * _queries.size());
        for (int query_id = 0; query_id < query_count(); query_id++) {
            const Query& query = _queries[query_id];
            prefix_events.push_back(PrefixEvent{
                query.x_upper, query.y_upper, query_id, false
            });
            prefix_events.push_back(PrefixEvent{
                query.x_lower, query.y_upper, query_id, true
            });
            prefix_events.push_back(PrefixEvent{
                query.x_upper, query.y_lower, query_id, true
            });
            prefix_events.push_back(PrefixEvent{
                query.x_lower, query.y_lower, query_id, false
            });
        }
        std::sort(
            prefix_events.begin(),
            prefix_events.end(),
            [](const PrefixEvent& first, const PrefixEvent& second) {
                return first.x < second.x;
            }
        );

        FenwickTree<Coefficient> fenwick(int(y_coordinates.size()));
        int point_index = 0;
        for (const PrefixEvent& event : prefix_events) {
            while (
                point_index < int(point_events.size()) &&
                point_events[point_index].x < event.x
            ) {
                const PointEvent& point = point_events[point_index];
                const int y_index = int(
                    std::lower_bound(
                        y_coordinates.begin(), y_coordinates.end(), point.y
                    ) - y_coordinates.begin()
                );
                fenwick.add(y_index, point.coefficient);
                point_index++;
            }
            const int y_count = int(
                std::lower_bound(
                    y_coordinates.begin(), y_coordinates.end(), event.y
                ) - y_coordinates.begin()
            );
            const T value = evaluate(fenwick.sum(y_count), event.x, event.y);
            if (event.subtract) {
                answers[event.query_id] -= value;
            } else {
                answers[event.query_id] += value;
            }
        }
        return answers;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_OFFLINE_RECTANGLE_ADD_RECTANGLE_SUM_HPP

#line 1 "ds/range_query/offline_rectangle_add_rectangle_sum.hpp"



#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

#line 1 "ds/range_query/fenwick_tree.hpp"



#line 6 "ds/range_query/fenwick_tree.hpp"

namespace m1une {
namespace ds {

template <typename T>
struct FenwickTree {
   private:
    int _n;
    int _max_power;
    std::vector<T> _data;

    static int max_power_leq(int n) {
        int result = 1;
        while (result <= n / 2) result <<= 1;
        return result;
    }

    T prefix_sum(int r) const {
        T result{};
        const T* data = _data.data();
        while (r > 0) {
            result += data[r];
            r -= r & -r;
        }
        return result;
    }

   public:
    FenwickTree() : _n(0), _max_power(0) {}

    explicit FenwickTree(int n)
        : _n(n), _max_power(max_power_leq(n > 0 ? n : 1)), _data(n + 1, T{}) {}

    explicit FenwickTree(const std::vector<T>& a)
        : _n(int(a.size())),
          _max_power(max_power_leq(_n > 0 ? _n : 1)),
          _data(a.size() + 1, T{}) {
        for (int i = 1; i <= _n; ++i) {
            _data[i] += a[i - 1];
            const int p = i + (i & -i);
            if (p <= _n) {
                _data[p] += _data[i];
            }
        }
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    // Adds `x` to the element at zero-based index `p`.
    void add(int p, const T& x) {
        assert(0 <= p && p < _n);
        ++p;
        T* data = _data.data();
        while (p <= _n) {
            data[p] += x;
            p += p & -p;
        }
    }

    // Returns the sum of elements in the range [0, r).
    T sum(int r) const {
        assert(0 <= r && r <= _n);
        return prefix_sum(r);
    }

    // Returns the sum of elements in the range [l, r).
    T sum(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        return prefix_sum(r) - prefix_sum(l);
    }

    // Returns the minimum index `r` such that the sum of [0, r) >= w.
    // Requires all elements in the tree to be non-negative.
    int lower_bound(T w) const {
        if (w <= 0) return 0;
        int x = 0;
        const T* data = _data.data();
        for (int k = _max_power; k > 0; k >>= 1) {
            if (x + k <= _n && data[x + k] < w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x + 1;
    }
};

}  // namespace ds
}  // namespace m1une


#line 10 "ds/range_query/offline_rectangle_add_rectangle_sum.hpp"

namespace m1une {
namespace ds {

// Records rectangle additions and rectangle-sum queries, then evaluates the
// complete static batch with an offline sweep.
template <class T, class X = long long, class Y = X>
class OfflineRectangleAddRectangleSum {
   public:
    using value_type = T;
    using x_type = X;
    using y_type = Y;

   private:
    struct Update {
        X x_lower;
        X x_upper;
        Y y_lower;
        Y y_upper;
        T value;
    };

    struct Query {
        X x_lower;
        X x_upper;
        Y y_lower;
        Y y_upper;
    };

    struct Coefficient {
        T xy{};
        T x{};
        T y{};
        T constant{};

        Coefficient& operator+=(const Coefficient& other) {
            xy += other.xy;
            x += other.x;
            y += other.y;
            constant += other.constant;
            return *this;
        }
    };

    struct PointEvent {
        X x;
        Y y;
        Coefficient coefficient;
    };

    struct PrefixEvent {
        X x;
        Y y;
        int query_id;
        bool subtract;
    };

    std::vector<Update> _updates;
    std::vector<Query> _queries;

    template <class Coordinate>
    static bool equivalent(const Coordinate& first, const Coordinate& second) {
        return !(first < second) && !(second < first);
    }

    static Coefficient make_coefficient(
        const X& x,
        const Y& y,
        const T& signed_value
    ) {
        const T converted_x(x);
        const T converted_y(y);
        return {
            signed_value,
            T{} - signed_value * converted_y,
            T{} - signed_value * converted_x,
            signed_value * converted_x * converted_y
        };
    }

    static T evaluate(
        const Coefficient& coefficient,
        const X& x,
        const Y& y
    ) {
        const T converted_x(x);
        const T converted_y(y);
        return coefficient.xy * converted_x * converted_y +
               coefficient.x * converted_x +
               coefficient.y * converted_y +
               coefficient.constant;
    }

   public:
    int update_count() const {
        return int(_updates.size());
    }

    int query_count() const {
        return int(_queries.size());
    }

    bool empty() const {
        return _updates.empty() && _queries.empty();
    }

    void reserve_updates(int capacity) {
        assert(0 <= capacity);
        _updates.reserve(capacity);
    }

    void reserve_queries(int capacity) {
        assert(0 <= capacity);
        _queries.reserve(capacity);
    }

    void clear() {
        _updates.clear();
        _queries.clear();
    }

    int add_rectangle(
        const X& x_lower,
        const X& x_upper,
        const Y& y_lower,
        const Y& y_upper,
        const T& value
    ) {
        assert(!(x_upper < x_lower));
        assert(!(y_upper < y_lower));
        const int id = update_count();
        _updates.push_back(Update{x_lower, x_upper, y_lower, y_upper, value});
        return id;
    }

    int add_query(
        const X& x_lower,
        const X& x_upper,
        const Y& y_lower,
        const Y& y_upper
    ) {
        assert(!(x_upper < x_lower));
        assert(!(y_upper < y_lower));
        const int id = query_count();
        _queries.push_back(Query{x_lower, x_upper, y_lower, y_upper});
        return id;
    }

    std::vector<T> calculate() const {
        std::vector<T> answers(_queries.size(), T{});
        if (_queries.empty() || _updates.empty()) return answers;

        std::vector<PointEvent> point_events;
        point_events.reserve(4 * _updates.size());
        std::vector<Y> y_coordinates;
        y_coordinates.reserve(2 * _updates.size());
        for (const Update& update : _updates) {
            if (equivalent(update.x_lower, update.x_upper) ||
                equivalent(update.y_lower, update.y_upper)) {
                continue;
            }
            const T negative_value = T{} - update.value;
            point_events.push_back(PointEvent{
                update.x_lower,
                update.y_lower,
                make_coefficient(update.x_lower, update.y_lower, update.value)
            });
            point_events.push_back(PointEvent{
                update.x_lower,
                update.y_upper,
                make_coefficient(update.x_lower, update.y_upper, negative_value)
            });
            point_events.push_back(PointEvent{
                update.x_upper,
                update.y_lower,
                make_coefficient(update.x_upper, update.y_lower, negative_value)
            });
            point_events.push_back(PointEvent{
                update.x_upper,
                update.y_upper,
                make_coefficient(update.x_upper, update.y_upper, update.value)
            });
            y_coordinates.push_back(update.y_lower);
            y_coordinates.push_back(update.y_upper);
        }
        if (point_events.empty()) return answers;

        std::sort(y_coordinates.begin(), y_coordinates.end());
        y_coordinates.erase(
            std::unique(
                y_coordinates.begin(),
                y_coordinates.end(),
                [](const Y& first, const Y& second) {
                    return equivalent(first, second);
                }
            ),
            y_coordinates.end()
        );
        std::sort(
            point_events.begin(),
            point_events.end(),
            [](const PointEvent& first, const PointEvent& second) {
                return first.x < second.x;
            }
        );

        std::vector<PrefixEvent> prefix_events;
        prefix_events.reserve(4 * _queries.size());
        for (int query_id = 0; query_id < query_count(); query_id++) {
            const Query& query = _queries[query_id];
            prefix_events.push_back(PrefixEvent{
                query.x_upper, query.y_upper, query_id, false
            });
            prefix_events.push_back(PrefixEvent{
                query.x_lower, query.y_upper, query_id, true
            });
            prefix_events.push_back(PrefixEvent{
                query.x_upper, query.y_lower, query_id, true
            });
            prefix_events.push_back(PrefixEvent{
                query.x_lower, query.y_lower, query_id, false
            });
        }
        std::sort(
            prefix_events.begin(),
            prefix_events.end(),
            [](const PrefixEvent& first, const PrefixEvent& second) {
                return first.x < second.x;
            }
        );

        FenwickTree<Coefficient> fenwick(int(y_coordinates.size()));
        int point_index = 0;
        for (const PrefixEvent& event : prefix_events) {
            while (
                point_index < int(point_events.size()) &&
                point_events[point_index].x < event.x
            ) {
                const PointEvent& point = point_events[point_index];
                const int y_index = int(
                    std::lower_bound(
                        y_coordinates.begin(), y_coordinates.end(), point.y
                    ) - y_coordinates.begin()
                );
                fenwick.add(y_index, point.coefficient);
                point_index++;
            }
            const int y_count = int(
                std::lower_bound(
                    y_coordinates.begin(), y_coordinates.end(), event.y
                ) - y_coordinates.begin()
            );
            const T value = evaluate(fenwick.sum(y_count), event.x, event.y);
            if (event.subtract) {
                answers[event.query_id] -= value;
            } else {
                answers[event.query_id] += value;
            }
        }
        return answers;
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Offline Rectangle Add Rectangle Sum
(ds/range_query/offline_rectangle_add_rectangle_sum.hpp)

Overview

Requirements

Interface

Operations

Example

Depends on

Verified with

Code

Offline Rectangle Add Rectangle Sum (ds/range_query/offline_rectangle_add_rectangle_sum.hpp)

Overview

Requirements

Interface

Operations

Example

Depends on

Verified with

Code

Offline Rectangle Add Rectangle Sum
(ds/range_query/offline_rectangle_add_rectangle_sum.hpp)