Loading [MathJax]/jax/output/CommonHTML/jax.js
My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

BIT 2D

コードについての説明

2 次元の BIT. "(i,j) に加算する" と "[0,i]×[0,j] の範囲の和を求める" の 2 つのクエリを効率よく処理するデータ構造.
x 軸方向に BIT の配列を持ってその配列の要素 11 つが y 軸方向の BIT 配列を持っている感じ.

時間計算量: add, sum O(log2n)
空間計算量: O(n2)

コード

  1. template<typename T> class BIT {
  2. private:
  3. int n,m; vector<vector<T> > bit;
  4. public:
  5. // (i, j) に val を加算する
  6. void add(int i, int j, T val){
  7. for(int i_ = i+1; i_ < n; i_ += i_ & -i_)
  8. for(int j_ = j+1; j_ < m; j_ += j_ & -j_)
  9. bit[i_][j_] += val;
  10. }
  11. // [0,i]×[0,j]の範囲の和を求める
  12. T sum(int i, int j){
  13. T s = 0;
  14. for(int i_ = i+1; i_ > 0; i_ -= i_ & -i_)
  15. for(int j_ = j+1; j_ > 0; j_ -= j_ & -j_)
  16. s += bit[i_][j_];
  17. return s;
  18. }
  19. // [lx, rx)×[ly, ry)の範囲の和を求める
  20. T sum(int lx, int rx, int ly, int ry){
  21. return sum(rx-1, ry-1) - sum(lx-1, ry-1) - sum(rx-1, ly-1) + sum(lx-1, ly-1);
  22. }
  23. BIT(int sz1, int sz2){
  24. n = sz1 + 1, m = sz2 + 1;
  25. bit.resize(n, vector<T>(m, 0));
  26. }
  27. BIT(vector<vector<T> >& v){
  28. n = (int)v.size() + 1, m = (int)v[0].size() + 1;
  29. bit.resize(n, vector<T>(m, 0));
  30. for(int i = 0; i < n - 1; i++)
  31. for(int j = 0; j < m - 1; j++)
  32. add(i, j, v[i][j]);
  33. }
  34. void print(){
  35. for(int i = 0; i < n; i++){
  36. for(int j = 0; j < m; j++){
  37. cout<< sum(i-1, i, j-1, j) << " ";
  38. }
  39. cout << "\n";
  40. }
  41. }
  42. void print_sum(){
  43. for(int i = 0; i < n; i++){
  44. for(int j = 0; j < m; j++){
  45. cout<< sum(i-1, j-1) << " ";
  46. }
  47. cout << "\n";
  48. }
  49. }
  50. };

verify 用の問題

AOJ : Planetary Exploration 提出コード(非想定解)