Static Point Add Rectangle Sum
(data-structure/static-point-add-rectangle-sum.hpp)

• View this file on GitHub
• Last update: 2026-08-26 13:48:57+09:00
• Include: #include "data-structure/static-point-add-rectangle-sum.hpp"

点への加算と長方形内の総和を offline で処理する．

StaticPointAddRectangleSum<T, I> として使う．座標の型 I の既定値は int，値の型 T は加減算が可能な型とする．長方形は半開領域 $[lx,rx)\times[ly,ry)$ で表す．

• query_add(x, y, value)：点 $(x,y)$ に value を加える操作を登録する．
• query_sum(lx, rx, ly, ry)：長方形内の点の値の総和を求めるクエリを登録する．
• calc()：登録順の総和クエリの答えを返す．

点とクエリの総数を $N$ として，calc() は $O(N\log N)$ 時間，$O(N)$ 空間．$x$ 座標順に走査し，$y$ 座標を Binary Indexed Tree で管理する．

資料

• Library Checker: Rectangle Sum

Depends on

• Binary Indexed Tree (data-structure/binary-indexed-tree.hpp)

Verified with

• verify/data-structure/LC_rectangle_sum.static_point_add.test.cpp

Code

#pragma once

#include "data-structure/binary-indexed-tree.hpp"

template <class T, class I = int>
struct StaticPointAddRectangleSum {
  void query_add(I x, I y, T v) { ps.push_back({x, y, v}); }
  void query_sum(I lx, I rx, I ly, I ry) {
    assert(lx <= rx && ly <= ry);
    qs.push_back({lx, rx, ly, ry});
  }
  vector<T> calc() const {
    struct E {
      I x, ly, ry;
      int q, s;
      bool operator<(const E& e) const { return x < e.x; }
    };
    vector<I> ys;
    ys.reserve(ps.size());
    for (auto [x, y, v] : ps) ys.push_back(y);
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    vector<P> a = ps;
    sort(a.begin(), a.end(), [](const P& p, const P& q) { return p.x < q.x; });
    vector<E> ev;
    ev.reserve(qs.size() * 2);
    for (int i = 0; i < (int)qs.size(); i++) {
      auto [lx, rx, ly, ry] = qs[i];
      ev.push_back({lx, ly, ry, i, -1});
      ev.push_back({rx, ly, ry, i, 1});
    }
    sort(ev.begin(), ev.end());
    BinaryIndexedTree<T> bit(ys.size());
    vector<T> ans(qs.size());
    int p = 0;
    for (auto [x, ly, ry, q, s] : ev) {
      while (p < (int)a.size() && a[p].x < x) {
        bit.add(LB(ys, a[p].y), a[p].v);
        p++;
      }
      T v = bit.sum(LB(ys, ly), LB(ys, ry));
      ans[q] += s == 1 ? v : -v;
    }
    return ans;
  }

 private:
  struct P {
    I x, y;
    T v;
  };
  struct Q {
    I lx, rx, ly, ry;
  };
  vector<P> ps;
  vector<Q> qs;
};

/**
 * @brief Static Point Add Rectangle Sum
 * @docs docs/data-structure/static-point-add-rectangle-sum.md
 */

#line 2 "data-structure/static-point-add-rectangle-sum.hpp"

#line 2 "data-structure/binary-indexed-tree.hpp"

template <class T>
struct BinaryIndexedTree {
  int size;
  vector<T> data;
  BinaryIndexedTree(int n) : size(n), data(n) {}
  void add(int p, T x) {
    for (p++; p <= size; p += p & -p) data[p - 1] += x;
  }
  T sum(int p) {
    T s = 0;
    for (; p; p -= p & -p) s += data[p - 1];
    return s;
  }
  T sum(int l, int r) { return sum(r) - sum(l); }

  template <bool (*f)(T)>
  int lower_bound() const {
    return lower_bound([](T x) { return f(x); });
  }
  template <class F>
  int lower_bound(F f) const {
    if (f(T(0))) return 0;
    int x = 0, r = 1;
    while (r < size) r = r << 1;
    T s = 0;
    for (int len = r; len > 0; len >>= 1) {
      if (x + len < size && !f(s + data[x + len]))
        s += data[x += len];
    }
    return x + 1;
  }
};

/**
 * @brief Binary Indexed Tree
 * @docs docs/data-structure/binary-indexed-tree.md
 */
#line 4 "data-structure/static-point-add-rectangle-sum.hpp"

template <class T, class I = int>
struct StaticPointAddRectangleSum {
  void query_add(I x, I y, T v) { ps.push_back({x, y, v}); }
  void query_sum(I lx, I rx, I ly, I ry) {
    assert(lx <= rx && ly <= ry);
    qs.push_back({lx, rx, ly, ry});
  }
  vector<T> calc() const {
    struct E {
      I x, ly, ry;
      int q, s;
      bool operator<(const E& e) const { return x < e.x; }
    };
    vector<I> ys;
    ys.reserve(ps.size());
    for (auto [x, y, v] : ps) ys.push_back(y);
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    vector<P> a = ps;
    sort(a.begin(), a.end(), [](const P& p, const P& q) { return p.x < q.x; });
    vector<E> ev;
    ev.reserve(qs.size() * 2);
    for (int i = 0; i < (int)qs.size(); i++) {
      auto [lx, rx, ly, ry] = qs[i];
      ev.push_back({lx, ly, ry, i, -1});
      ev.push_back({rx, ly, ry, i, 1});
    }
    sort(ev.begin(), ev.end());
    BinaryIndexedTree<T> bit(ys.size());
    vector<T> ans(qs.size());
    int p = 0;
    for (auto [x, ly, ry, q, s] : ev) {
      while (p < (int)a.size() && a[p].x < x) {
        bit.add(LB(ys, a[p].y), a[p].v);
        p++;
      }
      T v = bit.sum(LB(ys, ly), LB(ys, ry));
      ans[q] += s == 1 ? v : -v;
    }
    return ans;
  }

 private:
  struct P {
    I x, y;
    T v;
  };
  struct Q {
    I lx, rx, ly, ry;
  };
  vector<P> ps;
  vector<Q> qs;
};

/**
 * @brief Static Point Add Rectangle Sum
 * @docs docs/data-structure/static-point-add-rectangle-sum.md
 */

Back to top page