test/data-structure/BIT.test.cpp

View this file on GitHub
Last update: 2024-05-31 19:00:40+09:00
Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

Code

#define 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"
#define 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;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#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 {
   vector<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';
   }
}