SHARE
TWEET

Untitled

a guest May 19th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. struct node {
  6.     int left;
  7.     int right;
  8.     int max;
  9.     node * child_left;
  10.     node * child_right;
  11. };
  12.  
  13. node * build(int left, int right, std::vector<int> & a){
  14.  
  15.     node * res = new node;
  16.     res->left = left;
  17.     res->right = right;
  18.  
  19.     if (left == right){
  20.         res->child_left = nullptr;
  21.         res->child_right = nullptr;
  22.         res->max = a[left];
  23.     }   else {
  24.         int mid = (left + right) / 2;
  25.         res->child_left = build(left, mid, a);
  26.         res->child_right = build(mid + 1, right, a);
  27.         res->max = std::max(res->child_left->max, res->child_right->max);
  28.     }
  29.  
  30.     return res;
  31. }
  32.  
  33. int query(node * root, int left, int right){
  34.     if (right < root->left || left > root->right){
  35.         return -1;
  36.     }
  37.     if (left <= root->left && root->right <= right){
  38.         return root->max;
  39.     }
  40.     int ans1 = query(root->child_left, left, right);
  41.     int ans2 = query(root->child_right, left, right);
  42.     return std::max(ans1, ans2);
  43. }
  44.  
  45. void update(node * root, int i, int val){
  46.     if (i < root->left || i > root->right){
  47.         return;
  48.     }
  49.     if (root->left == root->right){
  50.         root->max = val;
  51.         return;
  52.     }
  53.     update(root->child_left, i, val);
  54.     update(root->child_right, i, val);
  55.     root->max = std::max(root->child_right->max, root->child_left->max);
  56. }
  57.  
  58.  
  59. int main() {
  60.     int n = 100;
  61.     std::vector<int> a(n + 1);
  62.     for (int i = 1; i < n + 1; ++i){
  63.         a[i] = i % 10;
  64.     }
  65.     node * root = build(1, n, a);
  66.     std::cout<<query(root, 23, 35)<<std::endl;
  67.     update(root, 29, 5);
  68.     std::cout<<query(root, 23, 35)<<std::endl;
  69.     update(root, 31, 100);
  70.     std::cout<<query(root, 23, 35)<<std::endl;
  71.     return 0;
  72. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top