test/data-structure/BIT.test.cpp

View this file on GitHub
Last update: 2026-07-19 04:18:57+09:00
Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum
#include "test/template.hpp"
#include "src/data-structure/BIT.hpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);

   ll N, Q;
   cin >> N >> Q;

   BIT A(N);
   rep(i, 0, N) {
      ll a;
      cin >> a;
      A.add(i, a);
   }

   while(Q--) {
      ll a, b, c;
      cin >> a >> b >> c;
      if(a == 0) A.add(b, c);
      else cout << A.sum(b, c) << '\n';
   }
}

#line 1 "test/data-structure/BIT.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum
#line 1 "test/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
template<class T> using V = vector<T>;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define each(i, a) for(auto&& i : a)
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#line 1 "src/data-structure/BIT.hpp"
struct BIT {
   V<ll> a;
   BIT(ll n) : a(n + 1) {}
   void add(ll i, ll x) {  // A[i] += x
      i++;
      while(i < sz(a)) {
         a[i] += x;
         i += i & -i;
      }
   }
   ll sum(ll r) {
      ll s = 0;
      while(r) {
         s += a[r];
         r -= r & -r;
      }
      return s;
   }
   ll sum(ll l, ll r) {  // sum of A[l, r)
      return sum(r) - sum(l);
   }
};
#line 4 "test/data-structure/BIT.test.cpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);

   ll N, Q;
   cin >> N >> Q;

   BIT A(N);
   rep(i, 0, N) {
      ll a;
      cin >> a;
      A.add(i, a);
   }

   while(Q--) {
      ll a, b, c;
      cin >> a >> b >> c;
      if(a == 0) A.add(b, c);
      else cout << A.sum(b, c) << '\n';
   }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	3 ms	4 MB
g++	max_random_00	AC	155 ms	7 MB
g++	max_random_01	AC	156 ms	7 MB
g++	max_random_02	AC	158 ms	7 MB
g++	max_random_03	AC	156 ms	7 MB
g++	max_random_04	AC	159 ms	7 MB
g++	random_00	AC	121 ms	6 MB
g++	random_01	AC	136 ms	7 MB
g++	random_02	AC	84 ms	4 MB
g++	random_03	AC	39 ms	7 MB
g++	random_04	AC	46 ms	6 MB
g++	small_00	AC	3 ms	4 MB
g++	small_01	AC	2 ms	4 MB
g++	small_02	AC	2 ms	4 MB
g++	small_03	AC	2 ms	4 MB
g++	small_04	AC	2 ms	4 MB
g++	small_05	AC	2 ms	4 MB
g++	small_06	AC	2 ms	4 MB
g++	small_07	AC	2 ms	4 MB
g++	small_08	AC	2 ms	4 MB
g++	small_09	AC	2 ms	4 MB