test/yosupo/BIT.test.cpp

• View this file on GitHub
• Last update: 2020-09-23 00:56:45+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• Binary Indexed Tree (data-structure/BIT.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include <bits/stdc++.h>
#include "../../data-structure/BIT.hpp"

#define REP(a,b) for(int a=0;a<(int)(b);++a)

int main(){
 int n, q;
 std::cin >> n >> q;

 BIT<long long> bit(n);
 REP(i, n) {
  int a;
  std::cin >> a;
  bit.add(i, a);
 }
 REP(_, q) {
  int type, l, r;
  std::cin >> type >> l >> r;
  if (type == 0) bit.add(l, r);
  else std::cout << bit.sum(l, r) << '\n';
 }
}

#line 1 "test/yosupo/BIT.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include <bits/stdc++.h>
#line 1 "data-structure/BIT.hpp"
// @brief Binary Indexed Tree
// @shortcut BIT
// @description BIT(Fenwick木)．単点更新区間和をO(logN)で行う．
// @docs data-structure/BIT.md
template <class T = int>
struct BIT {
 int N;
 std::vector<T> bit;
 BIT() : N(0) {}
 BIT(int n) : N(n), bit(N + 1, 0) {}
 BIT(int n, T init) : N(n), bit(N + 1, init) {}

 // bit[i] += w;
 void add(int i, T w) { 
  for (int x = ++i; x <= N; x += x & -x) bit[x] += w;
 }
 // return sum [0, i);
 T sum(int i) {
  T res = 0;
  for (int x = i; x > 0; x -= x & -x) res += bit[x];
  return res;
 }
 // return sum [i, j);
 T sum(int i, int j) { return sum(j) - sum(i); }
 const T& operator[](const int& i) const { return bit[i]; }
};
#line 4 "test/yosupo/BIT.test.cpp"

#define REP(a,b) for(int a=0;a<(int)(b);++a)

int main(){
 int n, q;
 std::cin >> n >> q;

 BIT<long long> bit(n);
 REP(i, n) {
  int a;
  std::cin >> a;
  bit.add(i, a);
 }
 REP(_, q) {
  int type, l, r;
  std::cin >> type >> l >> r;
  if (type == 0) bit.add(l, r);
  else std::cout << bit.sum(l, r) << '\n';
 }
}

Back to top page