Offline 2D Sum (Rectangle Sum)
(structure/offline_2dsum.hpp)

• View this file on GitHub
• Last update: 2026-01-24 17:34:48+09:00
• Include: #include "structure/offline_2dsum.hpp"

2次元平面上の点に重みを加え、長方形領域内の重みの総和を求めるクエリをオフラインで処理します。

コンストラクタ

offline_2dsum<T, W>()

T: 座標の型, W: 重みの型

add_point

void add_point(T x, T y, W w)

点 $(x, y)$ に重み $w$ を追加する。

計算量

• $O(1)$

add_query

void add_query(T l, T r, T d, T u)

領域 $[l, r) \times [d, u)$ の重みの総和を求めるクエリを追加する。 つまり、$l \le x < r, d \le y < u$ を満たす点の重みの総和を求める。

計算量

• $O(1)$

solve

std::vector<W> solve()

追加されたすべてのクエリに対する解答を計算し、追加された順に返す。

計算量

点の個数を $N$、クエリの個数を $Q$ とすると

• $O(N \log N + Q \log Q + (N + Q) \log N)$

Depends on

• structure/fenwick_tree.hpp

Verified with

• test/verify/structure/yosupo-rectangle-sum.test.cpp

Code

#ifndef HARUILIB_STRUCTURE_OFFLINE_2DSUM_HPP
#define HARUILIB_STRUCTURE_OFFLINE_2DSUM_HPP

#include <vector>
#include <algorithm>
#include "structure/fenwick_tree.hpp"

template <class T, class W> struct offline_2dsum {
  struct Point {
    T x, y;
    W w;
  };
  struct Query {
    T l, r, d, u;
  };

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

  void add_query(T l, T r, T d, T u) {
    queries.push_back({l, r, d, u});
  }

  std::vector<W> solve() {
    int n = points.size();
    int q = queries.size();
    std::vector<W> res(q, 0);

    std::vector<T> ys;
    ys.reserve(n);
    for (auto& p : points) ys.push_back(p.y);
    std::sort(ys.begin(), ys.end());
    ys.erase(std::unique(ys.begin(), ys.end()), ys.end());

    auto get_y = [&](T y) {
      return std::lower_bound(ys.begin(), ys.end(), y) - ys.begin();
    };

    struct Event {
      T x;
      int d, u;
      int id;
      int type; // -1 for l, 1 for r
      bool operator<(const Event& other) const {
        if (x != other.x) return x < other.x;
        return type < other.type;
      }
    };

    std::vector<Event> events;
    events.reserve(2 * q);
    for (int i = 0; i < q; i++) {
      int d = get_y(queries[i].d);
      int u = get_y(queries[i].u);
      events.push_back({queries[i].l, d, u, i, -1});
      events.push_back({queries[i].r, d, u, i, 1});
    }

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

    fenwick_tree<W> ft(ys.size());
    int pi = 0;
    for (auto& e : events) {
      while (pi < n && points[pi].x < e.x) {
        ft.add(get_y(points[pi].y), points[pi].w);
        pi++;
      }
      res[e.id] += (W)e.type * ft.sum(e.d, e.u);
    }

    return res;
  }

private:
  std::vector<Point> points;
  std::vector<Query> queries;
};

#endif // HARUILIB_STRUCTURE_OFFLINE_2DSUM_HPP

#line 1 "structure/offline_2dsum.hpp"



#include <vector>
#include <algorithm>
#line 1 "structure/fenwick_tree.hpp"



#line 5 "structure/fenwick_tree.hpp"
#include <cassert>

template <class T> struct fenwick_tree {
  fenwick_tree(): _n(0) {}
  explicit fenwick_tree(int n): _n(n), data(n) {}

  // point add
  void add(int p, T x) {
    assert(0 <= p && p < _n);
    p++;
    while (p <= _n) {
      data[p-1] += T(x);
      p += p & -p;
    }
  } 

  T sum(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    return sum(r) - sum(l);
  }

private:
  int _n;
  std::vector<T> data;
  T sum(int r) {
    T ret(0);
    while (r > 0) {
      ret += data[r-1];
      r -= r & -r;
    }

    return ret;
  }
};


#line 7 "structure/offline_2dsum.hpp"

template <class T, class W> struct offline_2dsum {
  struct Point {
    T x, y;
    W w;
  };
  struct Query {
    T l, r, d, u;
  };

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

  void add_query(T l, T r, T d, T u) {
    queries.push_back({l, r, d, u});
  }

  std::vector<W> solve() {
    int n = points.size();
    int q = queries.size();
    std::vector<W> res(q, 0);

    std::vector<T> ys;
    ys.reserve(n);
    for (auto& p : points) ys.push_back(p.y);
    std::sort(ys.begin(), ys.end());
    ys.erase(std::unique(ys.begin(), ys.end()), ys.end());

    auto get_y = [&](T y) {
      return std::lower_bound(ys.begin(), ys.end(), y) - ys.begin();
    };

    struct Event {
      T x;
      int d, u;
      int id;
      int type; // -1 for l, 1 for r
      bool operator<(const Event& other) const {
        if (x != other.x) return x < other.x;
        return type < other.type;
      }
    };

    std::vector<Event> events;
    events.reserve(2 * q);
    for (int i = 0; i < q; i++) {
      int d = get_y(queries[i].d);
      int u = get_y(queries[i].u);
      events.push_back({queries[i].l, d, u, i, -1});
      events.push_back({queries[i].r, d, u, i, 1});
    }

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

    fenwick_tree<W> ft(ys.size());
    int pi = 0;
    for (auto& e : events) {
      while (pi < n && points[pi].x < e.x) {
        ft.add(get_y(points[pi].y), points[pi].w);
        pi++;
      }
      res[e.id] += (W)e.type * ft.sum(e.d, e.u);
    }

    return res;
  }

private:
  std::vector<Point> points;
  std::vector<Query> queries;
};

Back to top page