Segtree 2D
(ds/segtree/segtree_2d.hpp)

View this file on GitHub
Last update: 2026-07-16 20:44:42+09:00
Include: #include "ds/segtree/segtree_2d.hpp"

Overview

m1une::ds::Segtree2D is a static compressed two-dimensional segment tree.

It supports:

point assignment on registered points
point access
rectangle product queries

The query rectangle is half-open:

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

All points that may be updated must be registered before construction.

Template Parameters

template <class Monoid, class X = int, class Y = X>
struct Segtree2D;

Monoid: the monoid used for aggregation.
X: the type of x-coordinates.
Y: the type of y-coordinates.

Monoid must satisfy m1une::monoid::IsMonoid.

The stored value type is:

using T = typename Monoid::value_type;

Coordinate Convention

This data structure is statically compressed.

That means every point (x, y) that may be updated must be given in the constructor or build.

For example, after constructing the data structure with points

{(1, 2), (3, 4)}

you may call:

seg.set(1, 2, value);
seg.set(3, 4, value);

but calling

seg.set(5, 6, value);

is invalid.

Construction

Empty constructor

Segtree2D()

Creates an empty data structure.

From coordinates

explicit Segtree2D(const std::vector<std::pair<X, Y>>& points)
explicit Segtree2D(std::vector<std::pair<X, Y>>&& points)

Creates a two-dimensional segment tree with the given registered points.

Duplicate points are removed automatically.

All values are initialized with Monoid::id().

From weighted points

explicit Segtree2D(const std::vector<std::tuple<X, Y, T>>& points)

Creates a two-dimensional segment tree with the given weighted points.

Each tuple represents (x, y, value).

If duplicate coordinates are given, the last set performed by the constructor determines the final value.

Methods

Let:

(N) be the number of registered distinct points
(X_N) be the number of distinct x-coordinates
(K_x) be the number of x-segment nodes visited by a query

Usually, (K_x = O(\log X_N)).

Method	Description	Complexity
`void build(std::vector<std::pair<X, Y>> points)`	Rebuilds the data structure from registered points. All values are reset to `Monoid::id()`.	(O(N \log^2 N))
`int size() const`	Returns the number of registered distinct points.	(O(1))
`bool empty() const`	Returns whether no point is registered.	(O(1))
`int x_size() const`	Returns the number of distinct x-coordinates.	(O(1))
`const std::vector<X>& xs() const`	Returns the compressed x-coordinates.	(O(1))
`bool contains_point(const X& x, const Y& y) const`	Returns whether `(x, y)` is registered.	(O(\log N))
`void set(const X& x, const Y& y, T value)`	Assigns `value` to the registered point `(x, y)`. Requires that `(x, y)` is registered.	(O(\log^2 N))
`T get(const X& x, const Y& y) const`	Returns the value at `(x, y)`. If the point is not registered, returns `Monoid::id()`.	(O(\log N))
`T operator()(const X& x, const Y& y) const`	Alias of `get(x, y)`.	(O(\log N))
`T prod(const X& xl, const X& xr, const Y& yl, const Y& yr) const`	Returns the product over registered points inside `[xl, xr) x [yl, yr)`.	(O(\log^2 N))
`T all_prod() const`	Returns the product over all registered points.	(O(1))
`std::vector<std::tuple<X, Y, T>> to_vector() const`	Returns all registered points with their current values.	(O(N))

Example

#include "ds/segtree/segtree_2d.hpp"
#include "monoid/add.hpp"

#include <cassert>
#include <iostream>
#include <vector>

int main() {
    using Sum = m1une::monoid::Add<long long>;

    std::vector<std::pair<int, int>> points = {
        {1, 2},
        {1, 5},
        {3, 4},
        {7, 1},
    };

    m1une::ds::Segtree2D<Sum> seg(points);

    seg.set(1, 2, 10);
    seg.set(1, 5, 20);
    seg.set(3, 4, 30);
    seg.set(7, 1, 40);

    assert(seg.get(1, 2) == 10);
    assert(seg.get(2, 2) == 0);

    assert(seg.prod(0, 4, 0, 10) == 60);
    assert(seg.prod(1, 2, 0, 10) == 30);
    assert(seg.prod(0, 10, 0, 3) == 50);
    assert(seg.all_prod() == 100);

    return 0;
}

Example: Static Rectangle Sum

This data structure can be used for static rectangle sum queries.

#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"

#include "../../../ds/segtree/segtree_2d.hpp"
#include "../../../monoid/add.hpp"

#include <iostream>
#include <tuple>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;

    using Sum = m1une::monoid::Add<long long>;

    std::vector<std::tuple<int, int, long long>> points;
    points.reserve(n);

    for (int i = 0; i < n; i++) {
        int x, y;
        long long w;
        std::cin >> x >> y >> w;
        points.emplace_back(x, y, w);
    }

    m1une::ds::Segtree2D<Sum> seg(points);

    while (q--) {
        int l, d, r, u;
        std::cin >> l >> d >> r >> u;
        std::cout << seg.prod(l, r, d, u) << '\n';
    }

    return 0;
}

Notes

This data structure is designed for the following situation:

all update positions are known in advance
values are updated by point assignment
queries are axis-aligned rectangle product queries

For point addition, use get and set together.

auto current = seg.get(x, y);
seg.set(x, y, current + delta);

For rectangle updates and point queries, use DualSegtree2D.

Although the template only requires a monoid, rectangle aggregation is usually intended for commutative monoids such as sum, min, max, and gcd. For non-commutative monoids, the result follows the internal traversal order and may not match a natural geometric interpretation.

Depends on

Verified with

verify/ds/segtree/segtree_2d.test.cpp

Code

#ifndef M1UNE_SEGTREE_2D_HPP
#define M1UNE_SEGTREE_2D_HPP 1

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

#include "../../math/bit_ceil.hpp"
#include "../../monoid/concept.hpp"

namespace m1une {
namespace ds {

// A static compressed 2D segment tree.
// It supports point assignment on registered points and rectangle product queries.
//
// The query rectangle is [xl, xr) x [yl, yr).
// All points that may be updated must be registered before construction.
template <class Monoid, class X = int, class Y = X>
requires m1une::monoid::IsMonoid<Monoid>
struct Segtree2D {
    using T = typename Monoid::value_type;
    using point_type = std::pair<X, Y>;
    using weighted_point_type = std::tuple<X, Y, T>;

private:
    int _n;
    int _size;
    int _point_count;
    std::vector<X> _xs;
    std::vector<std::vector<Y>> _ys;
    std::vector<std::vector<T>> _d;

    static std::vector<point_type> normalize_points(std::vector<point_type> points) {
        std::sort(points.begin(), points.end());
        points.erase(std::unique(points.begin(), points.end()), points.end());
        return points;
    }

    int x_index(const X& x) const {
        auto it = std::lower_bound(_xs.begin(), _xs.end(), x);
        if (it == _xs.end() || *it != x) return -1;
        return int(it - _xs.begin());
    }

    int y_index(int k, const Y& y) const {
        const auto& ys = _ys[k];
        auto it = std::lower_bound(ys.begin(), ys.end(), y);
        if (it == ys.end() || *it != y) return -1;
        return int(it - ys.begin());
    }

    T get_exact(int k, const Y& y) const {
        int pos = y_index(k, y);
        if (pos == -1) return Monoid::id();
        int m = int(_ys[k].size());
        return _d[k][m + pos];
    }

    void set_exact(int k, const Y& y, T x) {
        int pos = y_index(k, y);
        assert(pos != -1);

        int m = int(_ys[k].size());
        int p = m + pos;

        _d[k][p] = std::move(x);
        while (1 < p) {
            p >>= 1;
            _d[k][p] = Monoid::op(_d[k][2 * p], _d[k][2 * p + 1]);
        }
    }

    T prod_y(int k, const Y& yl, const Y& yr) const {
        assert(yl <= yr);
        if (yl == yr || _ys[k].empty()) return Monoid::id();

        const auto& ys = _ys[k];
        int l = int(std::lower_bound(ys.begin(), ys.end(), yl) - ys.begin());
        int r = int(std::lower_bound(ys.begin(), ys.end(), yr) - ys.begin());

        int m = int(ys.size());
        l += m;
        r += m;

        T sml = Monoid::id();
        T smr = Monoid::id();

        while (l < r) {
            if (l & 1) sml = Monoid::op(sml, _d[k][l++]);
            if (r & 1) smr = Monoid::op(_d[k][--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return Monoid::op(sml, smr);
    }

public:
    Segtree2D() : _n(0), _size(1), _point_count(0), _ys(2), _d(2) {}

    explicit Segtree2D(const std::vector<point_type>& points) {
        build(points);
    }

    explicit Segtree2D(std::vector<point_type>&& points) {
        build(std::move(points));
    }

    explicit Segtree2D(const std::vector<weighted_point_type>& points) {
        std::vector<point_type> coords;
        coords.reserve(points.size());

        for (const auto& [x, y, value] : points) {
            (void)value;
            coords.emplace_back(x, y);
        }

        build(std::move(coords));

        for (const auto& [x, y, value] : points) {
            set(x, y, value);
        }
    }

    void build(std::vector<point_type> points) {
        points = normalize_points(std::move(points));

        _point_count = int(points.size());

        _xs.clear();
        _xs.reserve(points.size());

        for (const auto& [x, y] : points) {
            (void)y;
            if (_xs.empty() || _xs.back() != x) _xs.push_back(x);
        }

        _n = int(_xs.size());
        _size = int(m1une::math::bit_ceil((unsigned int)std::max(1, _n)));

        _ys.assign(2 * _size, {});
        _d.assign(2 * _size, {});

        for (const auto& [x, y] : points) {
            int xi = int(std::lower_bound(_xs.begin(), _xs.end(), x) - _xs.begin());
            for (int k = xi + _size; k; k >>= 1) {
                _ys[k].push_back(y);
            }
        }

        for (int k = 1; k < 2 * _size; k++) {
            auto& ys = _ys[k];
            std::sort(ys.begin(), ys.end());
            ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
            _d[k].assign(2 * ys.size(), Monoid::id());
        }
    }

    int size() const {
        return _point_count;
    }

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

    int x_size() const {
        return _n;
    }

    const std::vector<X>& xs() const {
        return _xs;
    }

    bool contains_point(const X& x, const Y& y) const {
        int xi = x_index(x);
        if (xi == -1) return false;
        return y_index(xi + _size, y) != -1;
    }

    void set(const X& x, const Y& y, T value) {
        int xi = x_index(x);
        assert(xi != -1);
        assert(y_index(xi + _size, y) != -1);

        int k = xi + _size;
        set_exact(k, y, std::move(value));

        while (1 < k) {
            k >>= 1;
            set_exact(k, y, Monoid::op(get_exact(2 * k, y), get_exact(2 * k + 1, y)));
        }
    }

    T get(const X& x, const Y& y) const {
        int xi = x_index(x);
        if (xi == -1) return Monoid::id();
        return get_exact(xi + _size, y);
    }

    T operator()(const X& x, const Y& y) const {
        return get(x, y);
    }

    T prod(const X& xl, const X& xr, const Y& yl, const Y& yr) const {
        assert(xl <= xr);
        assert(yl <= yr);

        if (xl == xr || yl == yr || empty()) return Monoid::id();

        int l = int(std::lower_bound(_xs.begin(), _xs.end(), xl) - _xs.begin());
        int r = int(std::lower_bound(_xs.begin(), _xs.end(), xr) - _xs.begin());

        l += _size;
        r += _size;

        T sml = Monoid::id();
        T smr = Monoid::id();

        while (l < r) {
            if (l & 1) sml = Monoid::op(sml, prod_y(l++, yl, yr));
            if (r & 1) smr = Monoid::op(prod_y(--r, yl, yr), smr);
            l >>= 1;
            r >>= 1;
        }

        return Monoid::op(sml, smr);
    }

    T all_prod() const {
        if (empty() || _d[1].empty()) return Monoid::id();
        return _d[1][1];
    }

    std::vector<weighted_point_type> to_vector() const {
        std::vector<weighted_point_type> res;
        res.reserve(_point_count);

        for (int xi = 0; xi < _n; xi++) {
            int k = xi + _size;
            int m = int(_ys[k].size());

            for (int j = 0; j < m; j++) {
                res.emplace_back(_xs[xi], _ys[k][j], _d[k][m + j]);
            }
        }

        return res;
    }
};

} // namespace ds
} // namespace m1une

#endif // M1UNE_SEGTREE_2D_HPP

#line 1 "ds/segtree/segtree_2d.hpp"



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

#line 1 "math/bit_ceil.hpp"



namespace m1une {
namespace math {

template <typename T>
constexpr T bit_ceil(T n) {
    if (n <= 1) return 1;
    T x = 1;
    while (x < n) x <<= 1;
    return x;
}

}  // namespace math
}  // namespace m1une


#line 1 "monoid/concept.hpp"



#include <concepts>

namespace m1une {
namespace monoid {

// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
    // 1. Must define `value_type`
    typename M::value_type;

    // 2. Must have a static method `id()` returning `value_type`
    { M::id() } -> std::same_as<typename M::value_type>;

    // 3. Must have a static method `op(a, b)` returning `value_type`
    { M::op(a, b) } -> std::same_as<typename M::value_type>;
};

// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
    { M::inv(a) } -> std::same_as<typename M::value_type>;
};

// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;

}  // namespace monoid
}  // namespace m1une


#line 12 "ds/segtree/segtree_2d.hpp"

namespace m1une {
namespace ds {

// A static compressed 2D segment tree.
// It supports point assignment on registered points and rectangle product queries.
//
// The query rectangle is [xl, xr) x [yl, yr).
// All points that may be updated must be registered before construction.
template <class Monoid, class X = int, class Y = X>
requires m1une::monoid::IsMonoid<Monoid>
struct Segtree2D {
    using T = typename Monoid::value_type;
    using point_type = std::pair<X, Y>;
    using weighted_point_type = std::tuple<X, Y, T>;

private:
    int _n;
    int _size;
    int _point_count;
    std::vector<X> _xs;
    std::vector<std::vector<Y>> _ys;
    std::vector<std::vector<T>> _d;

    static std::vector<point_type> normalize_points(std::vector<point_type> points) {
        std::sort(points.begin(), points.end());
        points.erase(std::unique(points.begin(), points.end()), points.end());
        return points;
    }

    int x_index(const X& x) const {
        auto it = std::lower_bound(_xs.begin(), _xs.end(), x);
        if (it == _xs.end() || *it != x) return -1;
        return int(it - _xs.begin());
    }

    int y_index(int k, const Y& y) const {
        const auto& ys = _ys[k];
        auto it = std::lower_bound(ys.begin(), ys.end(), y);
        if (it == ys.end() || *it != y) return -1;
        return int(it - ys.begin());
    }

    T get_exact(int k, const Y& y) const {
        int pos = y_index(k, y);
        if (pos == -1) return Monoid::id();
        int m = int(_ys[k].size());
        return _d[k][m + pos];
    }

    void set_exact(int k, const Y& y, T x) {
        int pos = y_index(k, y);
        assert(pos != -1);

        int m = int(_ys[k].size());
        int p = m + pos;

        _d[k][p] = std::move(x);
        while (1 < p) {
            p >>= 1;
            _d[k][p] = Monoid::op(_d[k][2 * p], _d[k][2 * p + 1]);
        }
    }

    T prod_y(int k, const Y& yl, const Y& yr) const {
        assert(yl <= yr);
        if (yl == yr || _ys[k].empty()) return Monoid::id();

        const auto& ys = _ys[k];
        int l = int(std::lower_bound(ys.begin(), ys.end(), yl) - ys.begin());
        int r = int(std::lower_bound(ys.begin(), ys.end(), yr) - ys.begin());

        int m = int(ys.size());
        l += m;
        r += m;

        T sml = Monoid::id();
        T smr = Monoid::id();

        while (l < r) {
            if (l & 1) sml = Monoid::op(sml, _d[k][l++]);
            if (r & 1) smr = Monoid::op(_d[k][--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return Monoid::op(sml, smr);
    }

public:
    Segtree2D() : _n(0), _size(1), _point_count(0), _ys(2), _d(2) {}

    explicit Segtree2D(const std::vector<point_type>& points) {
        build(points);
    }

    explicit Segtree2D(std::vector<point_type>&& points) {
        build(std::move(points));
    }

    explicit Segtree2D(const std::vector<weighted_point_type>& points) {
        std::vector<point_type> coords;
        coords.reserve(points.size());

        for (const auto& [x, y, value] : points) {
            (void)value;
            coords.emplace_back(x, y);
        }

        build(std::move(coords));

        for (const auto& [x, y, value] : points) {
            set(x, y, value);
        }
    }

    void build(std::vector<point_type> points) {
        points = normalize_points(std::move(points));

        _point_count = int(points.size());

        _xs.clear();
        _xs.reserve(points.size());

        for (const auto& [x, y] : points) {
            (void)y;
            if (_xs.empty() || _xs.back() != x) _xs.push_back(x);
        }

        _n = int(_xs.size());
        _size = int(m1une::math::bit_ceil((unsigned int)std::max(1, _n)));

        _ys.assign(2 * _size, {});
        _d.assign(2 * _size, {});

        for (const auto& [x, y] : points) {
            int xi = int(std::lower_bound(_xs.begin(), _xs.end(), x) - _xs.begin());
            for (int k = xi + _size; k; k >>= 1) {
                _ys[k].push_back(y);
            }
        }

        for (int k = 1; k < 2 * _size; k++) {
            auto& ys = _ys[k];
            std::sort(ys.begin(), ys.end());
            ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
            _d[k].assign(2 * ys.size(), Monoid::id());
        }
    }

    int size() const {
        return _point_count;
    }

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

    int x_size() const {
        return _n;
    }

    const std::vector<X>& xs() const {
        return _xs;
    }

    bool contains_point(const X& x, const Y& y) const {
        int xi = x_index(x);
        if (xi == -1) return false;
        return y_index(xi + _size, y) != -1;
    }

    void set(const X& x, const Y& y, T value) {
        int xi = x_index(x);
        assert(xi != -1);
        assert(y_index(xi + _size, y) != -1);

        int k = xi + _size;
        set_exact(k, y, std::move(value));

        while (1 < k) {
            k >>= 1;
            set_exact(k, y, Monoid::op(get_exact(2 * k, y), get_exact(2 * k + 1, y)));
        }
    }

    T get(const X& x, const Y& y) const {
        int xi = x_index(x);
        if (xi == -1) return Monoid::id();
        return get_exact(xi + _size, y);
    }

    T operator()(const X& x, const Y& y) const {
        return get(x, y);
    }

    T prod(const X& xl, const X& xr, const Y& yl, const Y& yr) const {
        assert(xl <= xr);
        assert(yl <= yr);

        if (xl == xr || yl == yr || empty()) return Monoid::id();

        int l = int(std::lower_bound(_xs.begin(), _xs.end(), xl) - _xs.begin());
        int r = int(std::lower_bound(_xs.begin(), _xs.end(), xr) - _xs.begin());

        l += _size;
        r += _size;

        T sml = Monoid::id();
        T smr = Monoid::id();

        while (l < r) {
            if (l & 1) sml = Monoid::op(sml, prod_y(l++, yl, yr));
            if (r & 1) smr = Monoid::op(prod_y(--r, yl, yr), smr);
            l >>= 1;
            r >>= 1;
        }

        return Monoid::op(sml, smr);
    }

    T all_prod() const {
        if (empty() || _d[1].empty()) return Monoid::id();
        return _d[1][1];
    }

    std::vector<weighted_point_type> to_vector() const {
        std::vector<weighted_point_type> res;
        res.reserve(_point_count);

        for (int xi = 0; xi < _n; xi++) {
            int k = xi + _size;
            int m = int(_ys[k].size());

            for (int j = 0; j < m; j++) {
                res.emplace_back(_xs[xi], _ys[k][j], _d[k][m + j]);
            }
        }

        return res;
    }
};

} // namespace ds
} // namespace m1une

m1une's library

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

Segtree 2D
(ds/segtree/segtree_2d.hpp)

Overview

Template Parameters

Coordinate Convention

Construction

Empty constructor

From coordinates

From weighted points

Methods

Example

Example: Static Rectangle Sum

Notes

Depends on

Verified with

Code

Segtree 2D (ds/segtree/segtree_2d.hpp)

Overview

Template Parameters

Coordinate Convention

Construction

Empty constructor

From coordinates

From weighted points

Methods

Example

Example: Static Rectangle Sum

Notes

Depends on

Verified with

Code

Segtree 2D
(ds/segtree/segtree_2d.hpp)