test/verify/yosupo-point-add-range-sum.test.cpp

View this file on GitHub
Last update: 2025-03-23 14:07:18+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 "template/template.hpp"

#include <vector>
#include "structure/fenwick_tree.hpp"

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int N, Q; cin >> N >> Q;

  fenwick_tree<ll> fw(N);
  for (int i=0; i<N; i++) {
    int a; cin >> a;
    fw.add(i, a);
  }

  for (int q=0; q<Q; q++) {
    ll op, a, b; cin >> op >> a >> b;
    if (op == 0) {
      fw.add(a,b);
    }
    else {
      cout << fw.sum(a,b) << endl;
    }
  }
  return 0;
}

#line 1 "test/verify/yosupo-point-add-range-sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#line 1 "template/template.hpp"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 3 "test/verify/yosupo-point-add-range-sum.test.cpp"

#include <vector>
#line 1 "structure/fenwick_tree.hpp"



#line 6 "structure/fenwick_tree.hpp"

template <class T> struct fenwick_tree {
  fenwick_tree(): _n(0) {}
  explicit fenwick_tree(int n): _n(n), data(n) {}

  // point add
  void add(int p, T x) {
    assert(0 <= p && p < _n);
    p++;
    while (p <= _n) {
      data[p-1] += T(x);
      p += p & -p;
    }
  } 

  T sum(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    return sum(r) - sum(l);
  }

private:
  int _n;
  std::vector<T> data;
  T sum(int r) {
    T ret(0);
    while (r > 0) {
      ret += data[r-1];
      r -= r & -r;
    }

    return ret;
  }
};


#line 6 "test/verify/yosupo-point-add-range-sum.test.cpp"

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int N, Q; cin >> N >> Q;

  fenwick_tree<ll> fw(N);
  for (int i=0; i<N; i++) {
    int a; cin >> a;
    fw.add(i, a);
  }

  for (int q=0; q<Q; q++) {
    ll op, a, b; cin >> op >> a >> b;
    if (op == 0) {
      fw.add(a,b);
    }
    else {
      cout << fw.sum(a,b) << endl;
    }
  }
  return 0;
}