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

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

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

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

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

登録した操作の総数を $N$ として，calc() は $O(N\log N)$ 時間，$O(N)$ 空間．

アルゴリズム

長方形加算を 2 次元差分により 4 個の点イベントへ変換する．点イベント $(a,b,v)$ の 2 次元累積和における $(x,y)$ への寄与は

\[v(x-a)(y-b)=vxy-vay-vbx+vab\]

となる．$1,x,y,xy$ の係数を 4 本の Binary Indexed Tree で管理し，$x$ 座標順に走査する．

資料

• Library Checker: Static Rectangle Add Rectangle Sum

Verified with

• verify/data-structure/LC_static_rectangle_add_rectangle_sum.test.cpp

Code

#pragma once

template <class T, class I = int>
struct StaticRectangleAddRectangleSum {
  void query_add(I lx, I rx, I ly, I ry, T v) {
    assert(lx <= rx && ly <= ry);
    rs.push_back({lx, rx, ly, ry, 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 A {
      I x, y;
      T v;
      bool operator<(const A& a) const { return x < a.x; }
    };
    struct E {
      I x, y;
      int q, s;
      bool operator<(const E& e) const { return x < e.x; }
    };
    struct BIT {
      int n;
      vector<array<T, 4>> d;
      BIT(int n_) : n(n_), d(n_) {}
      void add(int p, array<T, 4> v) {
        for (p++; p <= n; p += p & -p)
          for (int k = 0; k < 4; k++) d[p - 1][k] += v[k];
      }
      array<T, 4> sum(int p) const {
        array<T, 4> s{};
        for (; p; p -= p & -p)
          for (int k = 0; k < 4; k++) s[k] += d[p - 1][k];
        return s;
      }
    };
    vector<I> ys;
    vector<A> as;
    as.reserve(rs.size() * 4);
    ys.reserve(rs.size() * 2);
    for (auto [lx, rx, ly, ry, v] : rs) {
      as.push_back({lx, ly, v});
      as.push_back({lx, ry, -v});
      as.push_back({rx, ly, -v});
      as.push_back({rx, ry, v});
      ys.push_back(ly);
      ys.push_back(ry);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    vector<E> ev;
    ev.reserve(qs.size() * 4);
    for (int i = 0; i < (int)qs.size(); i++) {
      auto [lx, rx, ly, ry] = qs[i];
      ev.push_back({lx, ly, i, 1});
      ev.push_back({lx, ry, i, -1});
      ev.push_back({rx, ly, i, -1});
      ev.push_back({rx, ry, i, 1});
    }
    sort(as.begin(), as.end());
    sort(ev.begin(), ev.end());
    BIT bit(ys.size());
    vector<T> ans(qs.size());
    int p = 0;
    for (auto [x, y, q, s] : ev) {
      while (p < (int)as.size() && as[p].x < x) {
        auto [ax, ay, v] = as[p++];
        bit.add(LB(ys, ay), {v * ax * ay, v * ax, v * ay, v});
      }
      auto v = bit.sum(LB(ys, y));
      T z = v[0] - v[1] * y - v[2] * x + v[3] * x * y;
      ans[q] += s == 1 ? z : -z;
    }
    return ans;
  }

 private:
  struct R {
    I lx, rx, ly, ry;
    T v;
  };
  struct Q { I lx, rx, ly, ry; };
  vector<R> rs;
  vector<Q> qs;
};

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

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

template <class T, class I = int>
struct StaticRectangleAddRectangleSum {
  void query_add(I lx, I rx, I ly, I ry, T v) {
    assert(lx <= rx && ly <= ry);
    rs.push_back({lx, rx, ly, ry, 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 A {
      I x, y;
      T v;
      bool operator<(const A& a) const { return x < a.x; }
    };
    struct E {
      I x, y;
      int q, s;
      bool operator<(const E& e) const { return x < e.x; }
    };
    struct BIT {
      int n;
      vector<array<T, 4>> d;
      BIT(int n_) : n(n_), d(n_) {}
      void add(int p, array<T, 4> v) {
        for (p++; p <= n; p += p & -p)
          for (int k = 0; k < 4; k++) d[p - 1][k] += v[k];
      }
      array<T, 4> sum(int p) const {
        array<T, 4> s{};
        for (; p; p -= p & -p)
          for (int k = 0; k < 4; k++) s[k] += d[p - 1][k];
        return s;
      }
    };
    vector<I> ys;
    vector<A> as;
    as.reserve(rs.size() * 4);
    ys.reserve(rs.size() * 2);
    for (auto [lx, rx, ly, ry, v] : rs) {
      as.push_back({lx, ly, v});
      as.push_back({lx, ry, -v});
      as.push_back({rx, ly, -v});
      as.push_back({rx, ry, v});
      ys.push_back(ly);
      ys.push_back(ry);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    vector<E> ev;
    ev.reserve(qs.size() * 4);
    for (int i = 0; i < (int)qs.size(); i++) {
      auto [lx, rx, ly, ry] = qs[i];
      ev.push_back({lx, ly, i, 1});
      ev.push_back({lx, ry, i, -1});
      ev.push_back({rx, ly, i, -1});
      ev.push_back({rx, ry, i, 1});
    }
    sort(as.begin(), as.end());
    sort(ev.begin(), ev.end());
    BIT bit(ys.size());
    vector<T> ans(qs.size());
    int p = 0;
    for (auto [x, y, q, s] : ev) {
      while (p < (int)as.size() && as[p].x < x) {
        auto [ax, ay, v] = as[p++];
        bit.add(LB(ys, ay), {v * ax * ay, v * ax, v * ay, v});
      }
      auto v = bit.sum(LB(ys, y));
      T z = v[0] - v[1] * y - v[2] * x + v[3] * x * y;
      ans[q] += s == 1 ? z : -z;
    }
    return ans;
  }

 private:
  struct R {
    I lx, rx, ly, ry;
    T v;
  };
  struct Q { I lx, rx, ly, ry; };
  vector<R> rs;
  vector<Q> qs;
};

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

Back to top page