tests/yosupo/segment_tree.point_add_range_sum.test.cpp

View this file on GitHub
Last update: 2020-10-28 19:21:59+01: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 "../../code/dataStructures/STIT.cc"

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int n, q;
  cin >> n >> q;

  auto f = [](auto a, auto b) { return a + b; };
  ST<ll, decltype(f)> st(n, 0, f);

  F0R(i, n)
    cin >> st.data[n + i];
  st.build();

  while(q--) {
    bool c;
    int l, r;
    cin >> c >> l >> r;
    if(!c)
      st.update(l, st.query(l, l + 1) + r);
    else
      cout << st.query(l, r) << endl;
  }
}

#line 1 "tests/yosupo/segment_tree.point_add_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/dataStructures/STIT.cc"
template<typename T, typename F>
struct ST {
  using value_type = T;
  using merge_type = F; 
  const int n;
  const T e;
  F merge;
  vector<T> data;
  ST(int sz, T _e, F m) : n{sz}, e{_e}, merge{m}, data(2 * n, e) {}
  void build() {
    for (int i = n - 1; i; --i)
      data[i] = merge(data[i << 1], data[i << 1 | 1]);
  }
  T query(int l, int r) {
    T li = e, ri = e;
    for (l += n, r += n; l < r; r >>= 1, l >>= 1) {
      if (l & 1) li = merge(li, data[l++]);
      if (r & 1) ri = merge(data[--r], ri);
    }
    return merge(li, ri);
  }
  void update(int i, T val) {
    for (data[i += n] = val; i > 1; i >>= 1)
      data[i >> 1] = merge(data[i & ~1], data[i | 1]);
  }
};
#line 4 "tests/yosupo/segment_tree.point_add_range_sum.test.cpp"

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int n, q;
  cin >> n >> q;

  auto f = [](auto a, auto b) { return a + b; };
  ST<ll, decltype(f)> st(n, 0, f);

  F0R(i, n)
    cin >> st.data[n + i];
  st.build();

  while(q--) {
    bool c;
    int l, r;
    cin >> c >> l >> r;
    if(!c)
      st.update(l, st.query(l, l + 1) + r);
    else
      cout << st.query(l, r) << endl;
  }
}