test/Library_Checker/Data_Structure/Point_Add_Range_Sum2.test.cpp

• View this file on GitHub
• Last update: 2026-05-07 01:17:17+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• data_structure/dynamicsegtree.hpp

Code

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

#include <iostream>
#include <vector>
#include "data_structure/dynamicsegtree.hpp"
using namespace std;
using ll = long long;

ll op(ll a, ll b) { return a + b;}
ll e() { return 0;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  vector<ll> a(n);
  for (ll &i: a) cin >> i;
  ayuna::DynamicSegmentTree<ll, op, e> st(n);
  for (int i = 0; i < n; i++) st.set(i, a[i]);
  while (q--) {
    int num;
    cin >> num;
    switch (num) {
    case 0:
      int p;
      ll x;
      cin >> p >> x;
      st.set(p, st.get(p) + x);
      break;

    case 1:
      int l, r;
      cin >> l >> r;
      cout << st.prod(l, r) << endl;
      break;
    }
  }
}

#line 1 "test/Library_Checker/Data_Structure/Point_Add_Range_Sum2.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#include <iostream>
#include <vector>
#line 2 "data_structure/dynamicsegtree.hpp"

#include <cassert>
#include <memory>

namespace ayuna {

template <class S, S (*op)(S, S), S (*e)()>
class DynamicSegmentTree {
public:
  DynamicSegmentTree(long long _n) : n(_n), root(nullptr) {}

  void set(long long p, S x) {
    assert(p < n);
    set(root, 0, n, p, x);
  }
  S get(long long p) const {
    assert(p < n);
    return get(root, 0, n, p);
  }
  S prod(long long l, long long r) const {
    assert(l <= r && r <= n);
    return prod(root, 0, n, l, r);
  }

  S all_prod() const { return root ? root->value : e(); }

  void reset(long long l, long long r) {
    assert(l <= r && r <= n);
    reset(root, 0, n, l, r);
  }

private:
  struct node;
  using node_ptr = std::unique_ptr<node>;

  struct node {
    S value;
    node_ptr left, right;
    node() : value(e()), left(nullptr), right(nullptr) {}
    node(S v) : value(v), left(nullptr), right(nullptr) {}
  };

  long long n;
  node_ptr root;

  void set(node_ptr &t, long long l, long long r, long long p, S x) {
    if(t == nullptr)
      t = std::make_unique<node>();
    if(r - l == 1) {
      t->value = x;
      return;
    }
    long long m = (l + r) >> 1;
    if(p < m)
      set(t->left, l, m, p, x);
    else
      set(t->right, m, r, p, x);
    t->value =
        op(t->left ? t->left->value : e(), t->right ? t->right->value : e());
  }

  S get(const node_ptr &t, long long l, long long r, long long p) const {
    if(t == nullptr)
      return e();
    if(r - l == 1)
      return t->value;
    long long m = (l + r) >> 1;
    if(p < m)
      return get(t->left, l, m, p);
    else
      return get(t->right, m, r, p);
  }

  S prod(const node_ptr &t, long long l, long long r, long long ql,
         long long qr) const {
    if(t == nullptr || r <= ql || qr <= l)
      return e();
    if(ql <= l && r <= qr)
      return t->value;
    long long m = (l + r) >> 1;
    return op(prod(t->left, l, m, ql, qr), prod(t->right, m, r, ql, qr));
  }

  void reset(node_ptr &t, long long l, long long r, long long ql,
             long long qr) {
    if(t == nullptr || r <= ql || qr <= l)
      return;
    if(ql <= l && r <= qr) {
      t.reset();
      return;
    }
    long long m = (l + r) >> 1;
    reset(t->left, l, m, ql, qr);
    reset(t->right, m, r, ql, qr);
    t->value =
        op(t->left ? t->left->value : e(), t->right ? t->right->value : e());
  }
};

} // namespace ayuna
#line 6 "test/Library_Checker/Data_Structure/Point_Add_Range_Sum2.test.cpp"
using namespace std;
using ll = long long;

ll op(ll a, ll b) { return a + b;}
ll e() { return 0;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  vector<ll> a(n);
  for (ll &i: a) cin >> i;
  ayuna::DynamicSegmentTree<ll, op, e> st(n);
  for (int i = 0; i < n; i++) st.set(i, a[i]);
  while (q--) {
    int num;
    cin >> num;
    switch (num) {
    case 0:
      int p;
      ll x;
      cin >> p >> x;
      st.set(p, st.get(p) + x);
      break;

    case 1:
      int l, r;
      cin >> l >> r;
      cout << st.prod(l, r) << endl;
      break;
    }
  }
}

Back to top page