Fshl0

Segment Tree

Apr 1st, 2020
235
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void upd(int v, int l, int r, int idx, int val) {
  2.     if (l == r) {
  3.         A[idx] = val;
  4.         tree[v] = val;
  5.         return;
  6.     }
  7.     int mid = (l + r) / 2;
  8.     if (l <= idx && idx <= mid)
  9.         upd(2 * v, l, mid, idx, val);
  10.     else upd(2 * v + 1 , mid + 1, r, idx, val);
  11.     tree[v] = min(tree[2 * v], tree[2 * v + 1]);
  12. }
  13.  
  14. void build(int v, int l, int r) {
  15.     if (l == r) {
  16.         tree[v] = A[l];
  17.         return;
  18.     }
  19.     int mid = (l + r) / 2;
  20.     build(2 * v, l, mid);
  21.     build(2 * v + 1, mid + 1, r);
  22.     tree[v] = min(tree[2 * v], tree[2 * v + 1]);
  23. }
  24.  
  25. int query(int v, int l, int r, int L, int R) {
  26.     if (R < l || r < L)
  27.         return INF;
  28.     if (L <= l && r <= R)
  29.         return tree[v];
  30.     int mid = (l + r) / 2;
  31.     int p1 = query(2 * v, l, mid, L, R);
  32.     int p2 = query(2 * v + 1, mid + 1, r, L, R);
  33.     return min(p1, p2);
  34. }
RAW Paste Data