test/ds/fw.test.cpp

• View this file on GitHub
• Last update: 2025-10-01 17:55:45+08:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• src/ds/ft.hpp
• src/misc/read.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#include "../../src/ds/ft.hpp"
#include "../../src/misc/read.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read(), q = read();
  FenwickTree<ll> fw(n);
  for (int i = 0; i < n; i++) {
    int a = read();
    fw.add(i, a);
  }
  while (q--) {
    int op = read();
    if (op == 0) {
      int p = read(), x = read();
      fw.add(p, x);
    } else {
      int l = read(), r = read();
      cout << fw.sum(l, r) << "\n";
    }
  }
  return 0;
}

#line 1 "test/ds/fw.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#line 1 "src/ds/ft.hpp"
template <typename T>
struct FenwickTree {
  int n;
  vector<T> c;
  FenwickTree(int n) : n(n), c(n) {}
  void add(int pos, T x) {
    for (int i = pos + 1; i <= n; i += i & -i) c[i - 1] += x;
  }
  T pref(int r) const {
    T ret = 0;
    for (int i = r; i > 0; i -= i & -i) ret += c[i - 1];
    return ret;
  }
  T sum(int l, int r) const { return pref(r) - pref(l); }
};
#line 1 "src/misc/read.hpp"
#define GC ch = getchar_unlocked()
ll read() {
  ll x = 0, f = 1, GC;
  while (ch < '0' || ch > '9') ch == '-' ? f = -1, GC : GC;
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', GC;
  return x * f;
}
#undef GC
#line 8 "test/ds/fw.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read(), q = read();
  FenwickTree<ll> fw(n);
  for (int i = 0; i < n; i++) {
    int a = read();
    fw.add(i, a);
  }
  while (q--) {
    int op = read();
    if (op == 0) {
      int p = read(), x = read();
      fw.add(p, x);
    } else {
      int l = read(), r = read();
      cout << fw.sum(l, r) << "\n";
    }
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	62 ms	7 MB
g++	max_random_01	AC	70 ms	7 MB
g++	max_random_02	AC	66 ms	7 MB
g++	max_random_03	AC	69 ms	7 MB
g++	max_random_04	AC	68 ms	7 MB
g++	random_00	AC	53 ms	6 MB
g++	random_01	AC	56 ms	7 MB
g++	random_02	AC	39 ms	4 MB
g++	random_03	AC	19 ms	7 MB
g++	random_04	AC	21 ms	6 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	4 ms	4 MB
g++	small_03	AC	4 ms	4 MB
g++	small_04	AC	4 ms	4 MB
g++	small_05	AC	4 ms	4 MB
g++	small_06	AC	4 ms	4 MB
g++	small_07	AC	4 ms	4 MB
g++	small_08	AC	4 ms	4 MB
g++	small_09	AC	4 ms	4 MB

Back to top page