peltorator

Down Segment Tree RMQ FAST

Apr 14th, 2021
363
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.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×