Guest User

Segment Tree

a guest
Jul 29th, 2020
105
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const int64_t INF = (int64_t)1e18 + 5;
  2.  
  3. struct SegmTree {
  4.   int n;
  5.   vector<int64_t> tree;
  6.  
  7.   SegmTree(int n_) : n(n_), tree(2 * n, INF) {}
  8.  
  9.   void Update(int l, int r, int64_t val) {
  10.     for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
  11.       if (l & 1) tree[l] = min(tree[l], val), ++l;
  12.       if (r & 1) --r, tree[r] = min(tree[r], val);
  13.     }
  14.   }
  15.  
  16.   int64_t Query(int pos) {
  17.     int64_t ans = INF;
  18.     for (pos += n; pos; pos /= 2)
  19.       ans = min(ans, tree[pos]);
  20.     return ans;
  21.   }
  22. };
RAW Paste Data