Complete Segment Tree Template

completesegtree.cpp

#include <bits/stdc++.h>
#define ll long long
#define FASTIO   \
  cin.tie(NULL); \
  ios::sync_with_stdio(false);
#define END return 0;
#define out cout <<
#define in cin >>
using namespace std;

struct SegmentTree {
  int n;
  vector<ll> tree;
  SegmentTree(int _n) : n(_n) { tree.resize(4 * n); }
  void build(const vector<ll>& a) { build(a, 1, 0, n - 1); }
  void build(const vector<ll>& a, int v, int l, int r) {
    if (l == r) {
      tree[v] = a[l];
    } else {
      int m = (l + r) / 2;
      build(a, v * 2, l, m);
      build(a, v * 2 + 1, m + 1, r);
      tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }
  }
  void update(int p, ll val) { update(1, 0, n - 1, p, val); }
  void update(int v, int l, int r, int p, ll val) {
    if (l == r) {
      tree[v] = val;
    } else {
      int m = (l + r) / 2;
      if (p <= m)
        update(v * 2, l, m, p, val);
      else
        update(v * 2 + 1, m + 1, r, p, val);
      tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }
  }
  ll query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return tree[v];
    int m = (l + r) / 2;
    return query(v * 2, l, m, ql, qr) + query(v * 2 + 1, m + 1, r, ql, qr);
  }
  ll query(int l, int r) { return query(1, 0, n - 1, l, r); }
};

struct NonRecursiveSegmentTree {
  int n;
  vector<ll> tree;
  BasicSegmentTree(int _n) : n(_n) { tree.resize(2 * n); }
  void build(const vector<ll>& a) {
    for (int i = 0; i < n; i++) tree[i + n] = a[i];
    for (int i = n - 1; i > 0; i--) tree[i] = tree[i * 2] + tree[i * 2 + 1];
  }
  void update(int p, ll val) {
    p += n;
    tree[p] = val;
    for (p /= 2; p > 0; p /= 2) tree[p] = tree[2 * p] + tree[2 * p + 1];
  }
  ll query(int l, int r) {
    l += n;
    r += n;
    ll res = 0;
    while (l <= r) {
      if (l % 2 == 1) res += tree[l++];
      if (r % 2 == 0) res += tree[r--];
      l /= 2;
      r /= 2;
    }
    return res;
  }
};

struct LazySegmentTree {
  int n;
  vector<ll> tree, lazy;
  LazySegmentTree(int _n) : n(_n) {
    tree.resize(4 * n);
    lazy.resize(4 * n);
  }
  void build(const vector<ll>& a) { build(1, 0, n - 1, a); }
  void build(int v, int l, int r, const vector<ll>& a) {
    if (l == r)
      tree[v] = a[l];
    else {
      int m = (l + r) / 2;
      build(v * 2, l, m, a);
      build(v * 2 + 1, m + 1, r, a);
      tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }
  }
  void push(int v, int l, int r) {
    if (lazy[v] != 0) {
      tree[v] += lazy[v] * (r - l + 1);
      if (l != r) {
        lazy[v * 2] += lazy[v];
        lazy[v * 2 + 1] += lazy[v];
      }
      lazy[v] = 0;
    }
  }
  void update(int l, int r, ll val) { update(1, 0, n - 1, l, r, val); }
  void update(int v, int l, int r, int ql, int qr, ll val) {
    push(v, l, r);
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
      lazy[v] += val;
      push(v, l, r);
    } else {
      int m = (l + r) / 2;
      update(v * 2, l, m, ql, qr, val);
      update(v * 2 + 1, m + 1, r, ql, qr, val);
      tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }
  }
  ll query(int ql, int qr) { return query(1, 0, n - 1, ql, qr); }
  ll query(int v, int l, int r, int ql, int qr) {
    push(v, l, r);
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return tree[v];
    int m = (l + r) / 2;
    return query(v * 2, l, m, ql, qr) + query(v * 2 + 1, m + 1, r, ql, qr);
  }
};

int main() {
  FASTIO
  int N, M, K;
  in N >> M >> K;
  vector<ll> a(N);
  for (int i = 0; i < N; i++) {
    in a[i];
  }
  BasicSegmentTree st(N);
  st.build(a);
  for (int i = 0; i < M + K; i++) {
    int t;
    in t;
    if (t == 1) {
      int b;
      ll c;
      in b >> c;
      st.update(b - 1, c);
    } else {
      int b, c;
      in b >> c;
      out st.query(b - 1, c - 1) << "\n";
    }
  }
  END
}