BITのテスト
(test/aoj/DSL_2_B.bit.test.cpp)

• View this file on GitHub
• Last update: 2021-04-15 20:24:09+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

Depends on

• BIT (Binary-Indexed-Tree) (datastructure/binary-indexed-tree.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"
// @title BITのテスト

#include "../../datastructure/binary-indexed-tree.hpp"

#include <iostream>
using namespace std;

int main() {
  int n, q; cin >> n >> q;
  BinaryIndexedTree<int> st(n);
  for (int i = 0; i < q; ++i) {
    int c, x, y; cin >> c >> x >> y; --x;
    if (c == 0) st.add(x, y);
    else cout << st.sum(x, y) << endl;
  }
}

#line 1 "test/aoj/DSL_2_B.bit.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"
// @title BITのテスト

#line 1 "datastructure/binary-indexed-tree.hpp"
/**
 * @title BIT (Binary-Indexed-Tree)
 * @see http://hos.ac/slides/20140319_bit.pdf
 */
#include <cassert>
#include <vector>

template <class T>
struct BinaryIndexedTree {
  int n;
  std::vector<T> bit;
  BinaryIndexedTree(int n): n(n), bit(n+1) {}

  void build(const std::vector<T> &v) {
    for (int x = 1; x <= n; ++x) bit[x] = v[x-1];
    for (int x = 1; x < n; ++x) bit[x + (x & -x)] += bit[x];
  }

  void add(int a, T w) { // 0-indexed
    assert(0 <= a && a < n);
    for (int x = a+1; x <= n; x += x & -x) bit[x] += w; // 1-indexed
  }

  T sum(int a) { // [0, a)
    assert(0 <= a && a <= n);
    T ret = 0;
    for (int x = a; x > 0; x -= x & -x) ret += bit[x]; // 1-indexed
    return ret;
  }

  T sum(int l, int r) { return sum(r)-sum(l); } // 0-indexed, [l, r)
};
#line 5 "test/aoj/DSL_2_B.bit.test.cpp"

#include <iostream>
using namespace std;

int main() {
  int n, q; cin >> n >> q;
  BinaryIndexedTree<int> st(n);
  for (int i = 0; i < q; ++i) {
    int c, x, y; cin >> c >> x >> y; --x;
    if (c == 0) st.add(x, y);
    else cout << st.sum(x, y) << endl;
  }
}

Back to top page