Advertisement
peltorator

Down Segment Tree RMQ FAST

Apr 14th, 2021
583
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int T = (1 << 21);
  6. int n;
  7.  
  8. int tree[T];
  9. int arr[T];
  10.  
  11. void build() {
  12.     for (int i = 0; i < n; i++) {
  13.         tree[i + n] = arr[i];
  14.     }
  15.     for (int i = n - 1; i >= 0; i--) {
  16.         tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
  17.     }
  18. }
  19.  
  20. void update(int pos, int val) {
  21.     pos += n;
  22.     tree[pos] = val;
  23.     for (tree[pos] = val; pos > 1; pos >>= 1) {
  24.         tree[pos >> 1] = min(tree[pos], tree[pos ^ 1]);
  25.     }
  26. }
  27.  
  28. int find_min(int ql, int qr) {
  29.     int ans = numeric_limits<int>::max();
  30.     ql += n;
  31.     qr += n;
  32.     while (ql < qr) {
  33.          if (ql & 1) {
  34.              ans = min(ans, tree[ql]);
  35.              ql++;
  36.          }
  37.          if (qr & 1) {
  38.              qr--;
  39.              ans = min(ans, tree[qr]);
  40.          }
  41.          ql >>= 1;
  42.          qr >>= 1;
  43.     }
  44.     return ans;
  45. }
  46.  
  47. int main() {
  48.     cin >> n;
  49.     for (int i = 0; i < n; i++) {
  50.         cin >> arr[i];
  51.     }
  52.     build();
  53.     int q;
  54.     cin >> q;
  55.     while (q--) {
  56.         char c;
  57.         cin >> c;
  58.         if (c == 'u') { // update
  59.             int pos, val;
  60.             cin >> pos >> val;
  61.             pos--; // 0-indexing
  62.             update(pos, val);
  63.         } else { // get
  64.             int ql, qr;
  65.             cin >> ql >> qr;
  66.             ql--; // 0-indexing, half-intervals
  67.             cout << find_min(ql, qr) << endl;
  68.         }
  69.     }
  70. }
  71.  
Advertisement
RAW Paste Data Copied
Advertisement