Segment Tree Summary

[neal2018]

Range Query, One Update

A segment tree is a data structure that updates and queries some interval characteristic in $O(\log{n})$.

In the code below, we store a basic segment tree for querying sum in t[2*n] array, which has twice the size of the original array.

Here is an example for the original array {1, 2, 3, 4}, and the segment tree is t = {0, 10, 3, 7, 1, 2, 3, 4}.

              t[1]=10
     +--------^---------+
     t[2]=3             t[3]=7
+----^----+        +----^----+
t[4]=1    t[5]=2   t[6]=3    t[7]=4                  

Note that we do not use t[0], but initialize it for insurance.

An interesting notice is that, in this indexing order, for index i, we arrive at its parent by i/2 and i's children by 2*i and 2*i+1.

#include <bits/stdc++.h>
using namespace std;

void build(int *t, int n) {
    // original array is in t[n:2n], now we fill t[:n]
    for (int i = n - 1; i > 0; --i) {
        t[i] = t[i * 2] + t[i * 2 + 1];
    }
    t[0] = 0;  // we do not use t[0], but initialize it for insurance
}

void modify(int p, int value, int *t, int n) {
    // update from leaf to root
    p += n;  // change to index in `t`
    t[p] = value;
    while (p > 1) {
        p /= 2;
        t[p] = t[p * 2] + t[p * 2 + 1];
    }
}

int query(int l, int r, int *t, int n) {
    // sum for [l, r), using a greedy approach
    int res = 0;
    l += n;  // change to index in `t`
    r += n;
    while (l < r) {
        if (l % 2 == 1) {
            // l is odd => l is the right child => we do not need
            // it's parents
            // => retrieve t[l] and move to right sibling of l's parent
            res += t[l];
            l++;
        }
        l /= 2;
        // else we move to l's parent, and try to retrieve it in next loop

        // we do not sum t[r], but need to keep r as the left-most no-need on
        // the right
        if (r % 2 == 1) {
            // r is odd => r is the right child => we only need its left sibling
            // => retrieve t[--r] and move to r's parent (we do not need r's
            // parent)
            r--;
            res += t[r];
        }
        r /= 2;  // else we do not need r or r's sibling, move to r's parent
    }
    return res;
}

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    int t[2 * n];  // we need twice space to store segment tree;

    for (int i = 0; i < n; i++) cin >> t[i + n];
    build(t, n);
    for (int i = 0; i < 2 * n; i++) cout << t[i] << " ";
    return 0;
}

def build(t, n):
    for i in reversed(range(1, n)):
        t[i] = t[2*i] + t[2*i+1]

def update(i, v, t, n):
    i += n
    t[i] = v
    while i > 1:
        i //= 2
        t[i] = t[2*i] + t[2*i+1]

def query(l, r, t, n):
    res = 0
    l += n
    r += n
    while l < r:
        if l % 2 == 1:
            res += t[l]
            l += 1
        l //= 2
        if r % 2 == 1:
            r -= 1
            res += t[r]
        r //= 2
    return res

Also, the code above is valid to an array with an arbitrary size, but the resulting tree structure will be a bit different.

Range Query, Range Update

LC 699

class SegmentTree:
    def __init__(self, n, update_fn, query_fn):
        self.n = n
        self.h = 1
        while (1 << self.h) < n:
            self.h += 1
        self.update_fn = update_fn
        self.query_fn = query_fn
        self.tree = [0] * (2 * n)
        self.lazy = [0] * n

    def _apply(self, x, val):
        self.tree[x] = self.update_fn(self.tree[x], val)
        if x < self.n:
            self.lazy[x] = self.update_fn(self.lazy[x], val)

    def _pull(self, x):
        while x > 1:
            x //= 2
            self.tree[x] = self.query_fn(self.tree[x * 2], self.tree[x * 2 + 1])
            self.tree[x] = self.update_fn(self.tree[x], self.lazy[x])

    def _push(self, x):
        for h in range(self.h, 0, -1):
            y = x >> h
            if self.lazy[y]:
                self._apply(y * 2, self.lazy[y])
                self._apply(y * 2 + 1, self.lazy[y])
                self.lazy[y] = 0

    def update(self, l, r, h):
        l += self.n
        r += self.n
        l0, r0 = l, r
        while l < r:
            if l & 1:
                self._apply(l, h)
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                self._apply(r, h)
            r //= 2
        self._pull(l0)
        self._pull(r0 - 1)

    def query(self, l, r):
        l += self.n
        r += self.n
        self._push(l)
        self._push(r - 1)
        ans = 0
        while l < r:
            if l & 1:
                ans = self.query_fn(ans, self.tree[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                ans = self.query_fn(ans, self.tree[r])
            r //= 2
        return ans

class Solution:
    def fallingSquares(self, positions):
        ls = set([p[0] for p in positions] + [p[0] + p[1] for p in positions])
        ss = sorted(ls)
        index = {v: i + 1 for i, v in enumerate(ss)}

        tree = SegmentTree(len(index) + 1, max, max)
        best = 0
        ans = []
        for left, size in positions:
            l, r = index[left], index[left + size]
            h = tree.query(l, r) + size
            tree.update(l, r, h)
            best = max(best, h)
            ans.append(best)
        return ans

[neal2018]

point update, range query

struct SegTree {
  ll n;
  vector<int> t;
  SegTree(ll _n) : n(_n), t(2 * n) {}
  void modify(ll p, int v) {
    t[p += n] += v;
    for (p /= 2; p; p /= 2) t[p] = t[2 * p] + t[2 * p + 1];
  }
  int query(ll l, ll r) {
    int res = 0;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) res += t[l++];
      if (r & 1) res += t[--r];
    }
    return res;
  }
};

struct Node {
  ll v = 0, init = 0;
};

Node pull(const Node &a, const Node &b) {
  if (!a.init) return b;
  if (!b.init) return a;
  Node c;
  return c;
}

struct SegTree {
  ll n;
  vector<Node> t;
  SegTree(ll _n) : n(_n), t(2 * n){};
  void modify(ll p, const Node &v) {
    t[p += n] = v;
    for (p /= 2; p; p /= 2) t[p] = pull(t[p * 2], t[p * 2 + 1]);
  }
  Node query(ll l, ll r) {
    Node left, right;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) left = pull(left, t[l++]);
      if (r & 1) right = pull(t[--r], right);
    }
    return pull(left, right);
  }
};

range update, point query

struct SegTree {
  int n;
  vector<ll> t;
  SegTree(int _n) : n(_n) { t.resize(2 * n); }
  void apply(ll x, ll v) { t[x] = (t[x] + v); }
  void modify(ll l, ll r, ll v) {
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) apply(l++, v);
      if (r & 1) apply(--r, v);
    }
  }
  ll query(ll p) {
    ll res = t[p += n];
    for (p /= 2; p > 0; p /= 2) res = (res + t[p]);
    return res;
  }
};

range update, range query (lazy tag)

struct Node {
  ll v = 0;
};
struct Tag {
  ll v = 0;
};
Node pull(const Node& a, const Node& b) { return {max(a.v, b.v)}; }

Tag pull(const Tag& a, const Tag& b) { return {a.v + b.v}; }

Node apply_tag(const Node& a, const Tag& b) { return {a.v + b.v}; }

struct SegTree {
  ll n, h;
  vector<Node> t;
  vector<Tag> lazy;
  SegTree(ll _n) : n(_n), h((ll)log2(n)), t(2 * _n), lazy(2 * _n) {}
  void apply(ll x, const Tag& tag) {
    t[x] = apply_tag(t[x], tag);
    lazy[x] = pull(lazy[x], tag);
  }
  void build(ll l) {
    for (l = (l + n) / 2; l > 0; l /= 2) {
      if (!lazy[l].v) t[l] = pull(t[l * 2], t[2 * l + 1]);
    }
  }
  void push(ll l) {
    for (ll s = h; s > 0; s--) {
      ll i = (l + n) >> s;
      if (lazy[i].v) apply(2 * i, lazy[i]), apply(2 * i + 1, lazy[i]);
      lazy[i] = Tag();
    }
  }
  void modify(ll l, ll r, const Tag& v) {
    push(l), push(r - 1);
    ll l0 = l, r0 = r;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) apply(l++, v);
      if (r & 1) apply(--r, v);
    }
    build(l0), build(r0 - 1);
  }
  Node query(ll l, ll r) {
    push(l), push(r - 1);
    Node left, right;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) left = pull(left, t[l++]);
      if (r & 1) right = pull(t[--r], right);
    }
    return pull(left, right);
  }
};

[neal2018]

range increase, range sum

#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct SegTree {
  ll n, h = 0;
  vector<ll> t, lazy;

  SegTree(ll n) : n(n) {
    t.resize(2 * n), lazy.resize(2 * n);
    while ((1 << h) < n) h++;
  }

  void apply(ll x, ll v, ll k) {
    t[x] += v * k;
    if (x < n) lazy[x] += v;
  }

  void build(ll l, ll r) {
    ll k = 2;
    for (l += n, r += n - 1; l > 1; k <<= 1) {
      l >>= 1, r >>= 1;
      for (ll i = r; i >= l; i--) {
        t[i] = t[i * 2] + t[i * 2 + 1] + lazy[i] * k;
      }
    }
  }

  void push(ll l, ll r) {
    ll s = h;
    for (l += n, r += n - 1; s > 0; s--) {
      for (ll i = l >> s; i <= r >> s; ++i) {
        apply(2 * i, lazy[i], 1 << (s - 1));
        apply(2 * i + 1, lazy[i], 1 << (s - 1));
        lazy[i] = 0;
      }
    }
  }

  void modify(ll l, ll r, ll v) {
    if (v == 0) return;
    push(l, l + 1), push(r - 1, r);
    ll l0 = l, r0 = r, k = 1;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) {
      if (l & 1) apply(l++, v, k);
      if (r & 1) apply(--r, v, k);
    }
    build(l0, l0 + 1), build(r0 - 1, r0);
  }

  ll query(ll l, ll r) {
    push(l, l + 1), push(r - 1, r);
    ll res = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res += t[l++];
      if (r & 1) res += t[--r];
    }
    return res;
  }
};

simplified

struct SegTree {
  ll n, h = 0;
  vector<ll> t, lazy;

  SegTree(ll n) : n(n), h(log2(n)), t(n * 2), lazy(n * 2) {}

  void apply(ll x, ll v, ll k) {
    t[x] += v * k;
    if (x < n) lazy[x] += v;
  }

  void build(ll l) {
    ll k = 2;
    for (l = (l + n) / 2; l > 0; k <<= 1, l >>= 1) {
      t[l] = t[l * 2] + t[l * 2 + 1] + lazy[l] * k;
    }
  }

  void push(ll l) {
    l += n;
    for (ll s = h; s > 0; s--) {
      int i = l >> s;
      apply(2 * i, lazy[i], 1 << (s - 1));
      apply(2 * i + 1, lazy[i], 1 << (s - 1));
      lazy[i] = 0;
    }
  }

  void modify(ll l, ll r, ll v) {
    if (v == 0) return;
    push(l), push(r - 1);
    ll l0 = l, r0 = r, k = 1;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) {
      if (l & 1) apply(l++, v, k);
      if (r & 1) apply(--r, v, k);
    }
    build(l0), build(r0 - 1);
  }

  ll query(ll l, ll r) {
    push(l), push(r - 1);
    ll res = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res += t[l++];
      if (r & 1) res += t[--r];
    }
    return res;
  }
};

range assign, range sum, be careful with 0

struct SegTree {
  ll n, h = 0;
  vector<ll> t, lazy;

  SegTree(ll _n) : n(_n), h((ll)log2(n)), t(n * 2), lazy(n * 2) {}

  void apply(ll x, ll v, ll k) {
    t[x] = v * k;
    if (x < n) lazy[x] = v;
  }

  void build(ll l) {
    ll k = 2;
    for (l = (l + n) / 2; l > 0; k <<= 1, l >>= 1) {
      if (lazy[l]) {
        t[l] = lazy[l] * k;
      } else {
        t[l] = t[l * 2] + t[l * 2 + 1];
      }
    }
  }

  void push(ll l) {
    l += n;
    for (ll s = h; s > 0; s--) {
      ll i = l >> s;
      if (lazy[i] == 0) continue;
      apply(2 * i, lazy[i], 1 << (s - 1));
      apply(2 * i + 1, lazy[i], 1 << (s - 1));
      lazy[i] = 0;
    }
  }

  void modify(ll l, ll r, ll v) {
    push(l), push(r - 1);
    ll l0 = l, r0 = r, k = 1;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) {
      if (l & 1) apply(l++, v, k);
      if (r & 1) apply(--r, v, k);
    }
    build(l0), build(r0 - 1);
  }

  ll query(ll l, ll r) {
    push(l), push(r - 1);
    ll res = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res += t[l++];
      if (r & 1) res += t[--r];
    }
    return res;
  }
};

[neal2018]

persistent, point update range query

struct Node {
  int lc, rc, p;
};

struct SegTree {
  int cnt = 0;
  vector<Node> t;
  SegTree(int n) : t(n * 20) {}
  int modify(int p, int l, int r, int x, int v) {
    // maintain the product of the range
    // p: original node, update a[x] -> a[x]*v
    int u = ++cnt;
    if (r - l == 1) {
      t[u].p = 1ll * t[p].p * v % MOD;
    } else {
      int m = (l + r) / 2;
      if (x < m) {
        t[u].lc = modify(t[p].lc, l, m, x, v);
        t[u].rc = t[p].rc;
      } else {
        t[u].lc = t[p].lc;
        t[u].rc = modify(t[p].rc, m, r, x, v);
      }
      t[u].p = 1ll * t[t[u].lc].p * t[t[u].rc].p % MOD;
    }
    return u;
  }
  int query(int p, int l, int r, int x, int y) {
    // query product a[x]...a[y-1] rooted at p
    // t[p] holds the info of [l, r)
    if (x <= l && r <= y) return t[p].p;
    int m = (l + r) / 2, res = 1;
    if (x < m) res = 1ll * res * query(t[p].lc, l, m, x, y) % MOD;
    if (y > m) res = 1ll * res * query(t[p].rc, m, r, x, y) % MOD;
    return res;
  }
};

dynamic add points

struct Node {
  int lc, rc, p;
};

struct SegTree {
  vector<Node> t = {{}};
  SegTree(int n) { t.reserve(n * 20); }
  int modify(int p, int l, int r, int x, int v) {
    // maintain the product of the range
    // p: original node, update a[x] -> a[x]*v
    t.push_back(t[p]);
    int u = t.size() - 1;
    if (r - l == 1) {
      t[u].p = 1ll * t[p].p * v % MOD;
    } else {
      int m = (l + r) / 2;
      if (x < m) {
        t[u].lc = modify(t[p].lc, l, m, x, v);
      } else {
        t[u].rc = modify(t[p].rc, m, r, x, v);
      }
      t[u].p = 1ll * t[t[u].lc].p * t[t[u].rc].p % MOD;
    }
    return u;
  }
  int query(int p, int l, int r, int x, int y) {
    // query product a[x]...a[y-1] rooted at p
    // t[p] holds the info of [l, r)
    if (x <= l && r <= y) return t[p].p;
    int m = (l + r) / 2, res = 1;
    if (x < m) res = 1ll * res * query(t[p].lc, l, m, x, y) % MOD;
    if (y > m) res = 1ll * res * query(t[p].rc, m, r, x, y) % MOD;
    return res;
  }
};

[neal2018]

Dynamic add point, range sum, single update, not persistent

struct Node {
  int lc = 0, rc = 0, p = 0;
};

struct DynamicSegTree {
  vector<Node> t = {{}};  // init all
  DynamicSegTree() = default;
  DynamicSegTree(int n) { t.reserve(n * 20); }
  int modify(int p, int l, int r, int x, int v) {
    // p: original node, update a[x] -> v
    int u = p;
    if (p == 0) t.push_back(t[p]), u = (int)t.size() - 1;
    if (r - l == 1) {
      t[u].p = v;
    } else {
      int mid = (l + r) / 2;
      if (x < mid) {
        t[u].lc = modify(t[p].lc, l, mid, x, v);
        t[u].rc = t[p].rc;
      } else {
        t[u].lc = t[p].lc;
        t[u].rc = modify(t[p].rc, mid, r, x, v);
      }
      t[u].p = t[t[u].lc].p + t[t[u].rc].p;
    }
    return u;
  }
  int query(int p, int l, int r, int x, int y) {
    // query sum a[x]...a[y-1] rooted at p
    // t[p] holds the info of [l, r)
    if (x <= l && r <= y) return t[p].p;
    int mid = (l + r) / 2, res = 0;
    if (x < mid) res += query(t[p].lc, l, mid, x, y);
    if (y > mid) res += query(t[p].rc, mid, r, x, y);
    return res;
  }
};

[neal2018]

st table

struct ST {
  vector<vector<int>> st;
  ST(vector<int>& a) {
    int sz = 1, n = int(a.size());
    while ((1 << sz) < n) sz++;
    st = vector(sz + 1, a);
    for (int k = 0, shift = 1; k < sz; k++, shift *= 2) {
      for (int i = 0; i + shift < n; i++) {
        st[k + 1][i] = max(st[k][i], st[k][i + shift]);
      }
    }
  }
  int query(int l, int r) {
    int level = 31 - __builtin_clz(r - l);
    return max(st[level][l], st[level][r - (1 << level)]);
  };
};

[neal2018]

2d ds

struct DynamicSegTree {
  struct Node {
    int lc = 0, rc = 0, p = 0;
  };
  vector<Node> t = {{}, {}};  // init all
  DynamicSegTree() = default;
  DynamicSegTree(int n) { t.reserve(n * 20); }
  int modify(int p, int l, int r, int x, int v) {
    // p: original node, update a[x] -> a[x] + v
    int u = p;
    if (p == 0) t.push_back(t[p]), u = (int)t.size() - 1;
    if (r - l == 1) {
      t[u].p += v;
    } else {
      int mid = (l + r) / 2;
      if (x < mid) {
        t[u].lc = modify(t[p].lc, l, mid, x, v);
        t[u].rc = t[p].rc;
      } else {
        t[u].lc = t[p].lc;
        t[u].rc = modify(t[p].rc, mid, r, x, v);
      }
      t[u].p = t[t[u].lc].p + t[t[u].rc].p;
    }
    return u;
  }
  int query(int p, int l, int r, int x, int y) {
    // query sum a[x]...a[y-1] rooted at p
    // t[p] holds the info of [l, r)
    if (x <= l && r <= y) return t[p].p;
    int mid = (l + r) / 2, res = 0;
    if (x < mid) res += query(t[p].lc, l, mid, x, y);
    if (y > mid) res += query(t[p].rc, mid, r, x, y);
    return res;
  }
};

struct Fenwick {
  int n;
  vector<DynamicSegTree> a;
  Fenwick(int _n) : n(_n), a(n) {}
  void add(int x, int y, int inc = 1) {
    // add inc # of (x, y)
    for (int i = x + 1; i <= n; i += i & -i) {
      a[i - 1].modify(1, 0, n, y, inc);
    }
  }
  int sum(int x, int y) {
    int res = 0;  // # in [0, 0] to (x, y)
    for (int i = x; i > 0; i -= i & -i) {
      res += a[i - 1].query(1, 0, n, 0, y);
    }
    return res;
  }
  int range_sum(int x1, int x2, int y) { return sum(x2, y) - sum(x1, y); }
  int range_sum(int x1, int y1, int x2, int y2) {
    return sum(x2, y2) + sum(x1, y1) - sum(x2, y1) - sum(x1, y2);
  }
};

struct SegTree {
  int n;
  vector<DynamicSegTree> t;
  SegTree(int _n) : n(_n), t(2 * n) {}
  void modify(int x, int y, int inc = 1) {
    for (x += n; x; x /= 2) t[x].modify(1, 0, n, y, inc);
  }
  int query(int x1, int y1, int x2, int y2) {
    int res = 0;
    for (x1 += n, x2 += n; x1 < x2; x1 /= 2, x2 /= 2) {
      if (x1 & 1) res += t[x1++].query(1, 0, n, y1, y2);
      if (x2 & 1) res += t[--x2].query(1, 0, n, y1, y2);
    }
    return res;
  }
};

[neal2018]

struct Node {
  int lc = 0, rc = 0, l = 0, r = 0;
  ll p = 0, lazy = 0;
};

struct DynamicSegTree {
  vector<Node> t = {{}, {}};  // init all
  DynamicSegTree() = default;
  DynamicSegTree(int n) { t.reserve(n * 20), t[1] = {0, 0, 0, n, 0, 0}; }
  void push(int p) {
    if (p == 0) return;
    int mid = (t[p].l + t[p].r) / 2;
    if (t[p].lc == 0) {
      t.push_back(t[0]), t[p].lc = (int)t.size() - 1;
      t[t[p].lc].l = t[p].l, t[t[p].lc].r = mid;
    }
    if (t[p].rc == 0) {
      t.push_back(t[0]), t[p].rc = (int)t.size() - 1;
      t[t[p].rc].l = mid, t[t[p].rc].r = t[p].r;
    }
    apply(t[p].lc, t[p].lazy), apply(t[p].rc, t[p].lazy);
    t[p].lazy = 0;
  }
  void apply(int p, ll v) { t[p].p += (t[p].r - t[p].l) * v, t[p].lazy += v; }
  void pull(int p) { t[p].p = t[t[p].lc].p + t[t[p].rc].p + (t[p].r - t[p].l) * t[p].lazy; }
  void modify(int p, int ql, int qr, ll v) {
    // p: original node, update a[x] -> a[x] + v
    if (ql <= t[p].l && t[p].r <= qr) return apply(p, v);
    push(p);
    int mid = (t[p].l + t[p].r) / 2;
    if (ql < mid) modify(t[p].lc, ql, qr, v);
    if (qr > mid) modify(t[p].rc, ql, qr, v);
    return pull(p);
  }
  ll query(int p, int ql, int qr) {
    // query sum a[ql]...a[qr-1] rooted at p
    // t[p] holds the info of [l, r)
    if (ql <= t[p].l && t[p].r <= qr) return t[p].p;
    push(p);
    int mid = (t[p].l + t[p].r) / 2;
    ll res = 0;
    if (ql < mid) res += query(t[p].lc, ql, qr);
    if (qr > mid) res += query(t[p].rc, ql, qr);
    return res;
  }
};

[neal2018]

2d fenwick

struct Fenwick2D {
  ll n, m;
  vector<vector<ll>> a;
  Fenwick2D(ll _n, ll _m) : n(_n), m(_m), a(n, vector<ll>(m)) {}
  void add(ll x, ll y, ll v) {
    // range add [(x1, y1), (n, m))
    for (ll i = x + 1; i <= n; i += i & -i) {
      for (ll j = y + 1; j <= m; j += j & -j) {
        a[i - 1][j - 1] += v;
      }
    }
  }
  void add(ll x1, ll y1, ll x2, ll y2, ll v) {
    // range add [(x1, y1), (x2, y2))
    add(x1, y1, v), add(x2, y2, v);
    add(x1, y2, -v), add(x2, y1, -v);
  }
  ll get(ll x, ll y) {
    // point get (x+1, y+1)
    ll ans = 0;
    for (ll i = x; i > 0; i -= i & -i) {
      for (ll j = y; j > 0; j -= j & -j) {
        ans += a[i - 1][j - 1];
      }
    }
    return ans;
  }
  ll get(ll x1, ll y1, ll x2, ll y2) {
    return get(x2, y2) + get(x1, y1) - get(x1, y2) - get(x2, y1);
  }
};

[neal2018]

n = 1e5, memory usage ~= 320M

struct Node {
  int lc = 0, rc = 0, l = 0, r = 0;
  ll p = 0, lazy = 0;
};

struct PersistentSegTree {
  vector<Node> t = {{}, {}};  // init all
  PersistentSegTree() = default;
  PersistentSegTree(int n, int limit) { t.reserve(n * 120), t[1] = {0, 0, 0, limit, 0, 0}; }
  void push(int p) {
    if (p == 0) return;
    int mid = (t[p].l + t[p].r) / 2;
    t[p].lc = apply(t[p].lc, t[p].lazy, t[p].l, mid);
    t[p].rc = apply(t[p].rc, t[p].lazy, mid, t[p].r);
    t[p].lazy = 0;
  }
  int apply(int u, ll v, int l, int r) {
    int p = (int)t.size();
    t.push_back(t[u]), t[p].l = l, t[p].r = r;
    t[p].p += (t[p].r - t[p].l) * v, t[p].lazy += v;
    return p;
  }
  int pull(int u) {
    int p = (int)t.size();
    t.push_back(t[u]);
    t[p].p = t[t[p].lc].p + t[t[p].rc].p + (t[p].r - t[p].l) * t[p].lazy;
    return p;
  }
  int modify(int p, int ql, int qr, ll v) {
    // p: original node, update a[x] -> a[x] + v
    // cout << p << " " << t[p].l << " " << t[p].r <<" "<<ql<<" "<<qr<< "\n";
    if (ql <= t[p].l && t[p].r <= qr) return apply(p, v, t[p].l, t[p].r);
    push(p);
    int mid = (t[p].l + t[p].r) / 2;
    if (ql < mid) t[p].lc = modify(t[p].lc, ql, qr, v);
    if (qr > mid) t[p].rc = modify(t[p].rc, ql, qr, v);
    return pull(p);
  }
  ll query(int p, int ql, int qr) {
    // query sum a[ql]...a[qr-1] rooted at p
    // t[p] holds the info of [l, r)
    if (ql <= t[p].l && t[p].r <= qr) return t[p].p;
    push(p);
    int mid = (t[p].l + t[p].r) / 2;
    ll res = 0;
    if (ql < mid) res += query(t[p].lc, ql, qr);
    if (qr > mid) res += query(t[p].rc, ql, qr);
    return res;
  }
};