data-structure/test/Point_Add_Range_Sum.test.cpp

• View this file on GitHub
• Last update: 2023-07-25 00:50:50+07:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• Fenwick Tree (data-structure/fenwick.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#include <bits/extc++.h>

using namespace std;

#include "data-structure/fenwick.hpp"

signed main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, q;
  cin >> n >> q;
  fenwick<int64_t> fw(n);
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    fw.add(i, x);
  }
  while (q--) {
    int t, l, r;
    cin >> t >> l >> r;
    if (t)
      cout << fw.sum(l, r) << '\n';
    else
      fw.add(l, r);
  }
}

#line 1 "data-structure/test/Point_Add_Range_Sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#include <bits/extc++.h>

using namespace std;

#line 1 "data-structure/fenwick.hpp"
template <typename T>
struct fenwick {
  fenwick(int n) : n(n), f(n + 1) {}

  // a[u] += val
  void add(int u, T val) {
    assert(0 <= u && u < n);
    ++u;
    while (u <= n) f[u] += val, u += u & -u;
  }

  // return the sum of [0, u)
  T sum(int u) const {
    assert(0 <= u && u <= n);
    T res = 0;
    while (u) res += f[u], u -= u & -u;
    return res;
  }

  // return the sum of [l, r)
  T sum(int l, int r) const {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return 0;
    return sum(r) - sum(l);
  }

  void reset() { fill(f.begin(), f.end(), T(0)); }

  int n;
  vector<T> f;
};
#line 8 "data-structure/test/Point_Add_Range_Sum.test.cpp"

signed main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, q;
  cin >> n >> q;
  fenwick<int64_t> fw(n);
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    fw.add(i, x);
  }
  while (q--) {
    int t, l, r;
    cin >> t >> l >> r;
    if (t)
      cout << fw.sum(l, r) << '\n';
    else
      fw.add(l, r);
  }
}

Back to top page