二次元Binary Indexed Tree
(data-structure-2d/2d-binary-indexed-tree.hpp)

• View this file on GitHub
• Last update: 2021-11-27 22:15:37+09:00
• Include: #include "data-structure-2d/2d-binary-indexed-tree.hpp"

Verified with

• verify/verify-aoj-dsl/aoj-dsl-5-b-bit2d.test.cpp

Code

#pragma once

template <typename T>
struct BinaryIndexedTree2D {
  int H, W;
  vector<vector<T>> bit;
  BinaryIndexedTree2D(int _H, int _W) : H(_H + 1), W(_W + 1) {
    bit.resize(H + 3, vector<T>(W + 3, 0));
  }
  // 関数の入力のindexは0-originを想定

  // (x,y)にwを足す
  // 範囲外の時は足さない
  void add(int x, int y, T w) {
    if (x < 0 || x >= H || y < 0 || y >= W) return;
    for (int a = (++y, ++x); a <= H; a += a & -a) {
      for (int b = y; b <= W; b += b & -b) {
        bit[a][b] += w;
      }
    }
  }

  // imos法で[(x1,y1) , (x2,y2)]にwを足す
  void imos(int x1, int y1, int x2, int y2, T w) {
    add(x1, y1, w);
    add(x1, y2 + 1, -w);
    add(x2 + 1, y1, -w);
    add(x2 + 1, y2 + 1, w);
  }

  //  [(0,0) , (x,y)]の和　閉区間に注意！
  // x,y<0の時は0 x>=H y>=Wのときはx=H-1,y=W-1とみなす
  // ( imos法の時は (x,y)の値を返す )
  T sum(int x, int y) {
    if (x < 0 || y < 0) return 0;
    if (x >= H) x = H - 1;
    if (y >= W) y = W - 1;
    T ret = 0;
    for (int a = (++y, ++x); a > 0; a -= a & -a) {
      for (int b = y; b > 0; b -= b & -b) {
        ret += bit[a][b];
      }
    }
    return ret;
  }

  // [(x1,y1) , (x2,y2)] の和
  // x1 > x2, y1 > y2の時はswap
  T sum(int x1, int y1, int x2, int y2) {
    if (x1 > x2 || y1 > y2) return T(0);
    return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) +
           sum(x1 - 1, y1 - 1);
  }
};

/*
 * @brief 二次元Binary Indexed Tree
 */

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

template <typename T>
struct BinaryIndexedTree2D {
  int H, W;
  vector<vector<T>> bit;
  BinaryIndexedTree2D(int _H, int _W) : H(_H + 1), W(_W + 1) {
    bit.resize(H + 3, vector<T>(W + 3, 0));
  }
  // 関数の入力のindexは0-originを想定

  // (x,y)にwを足す
  // 範囲外の時は足さない
  void add(int x, int y, T w) {
    if (x < 0 || x >= H || y < 0 || y >= W) return;
    for (int a = (++y, ++x); a <= H; a += a & -a) {
      for (int b = y; b <= W; b += b & -b) {
        bit[a][b] += w;
      }
    }
  }

  // imos法で[(x1,y1) , (x2,y2)]にwを足す
  void imos(int x1, int y1, int x2, int y2, T w) {
    add(x1, y1, w);
    add(x1, y2 + 1, -w);
    add(x2 + 1, y1, -w);
    add(x2 + 1, y2 + 1, w);
  }

  //  [(0,0) , (x,y)]の和　閉区間に注意！
  // x,y<0の時は0 x>=H y>=Wのときはx=H-1,y=W-1とみなす
  // ( imos法の時は (x,y)の値を返す )
  T sum(int x, int y) {
    if (x < 0 || y < 0) return 0;
    if (x >= H) x = H - 1;
    if (y >= W) y = W - 1;
    T ret = 0;
    for (int a = (++y, ++x); a > 0; a -= a & -a) {
      for (int b = y; b > 0; b -= b & -b) {
        ret += bit[a][b];
      }
    }
    return ret;
  }

  // [(x1,y1) , (x2,y2)] の和
  // x1 > x2, y1 > y2の時はswap
  T sum(int x1, int y1, int x2, int y2) {
    if (x1 > x2 || y1 > y2) return T(0);
    return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) +
           sum(x1 - 1, y1 - 1);
  }
};

/*
 * @brief 二次元Binary Indexed Tree
 */

Back to top page