spider68

Dynamic Range Minimum Queries

Jun 18th, 2021
956
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. #define ll long long
  5. struct SegmentTreeNode {
  6.     int start, end,sum;
  7.     SegmentTreeNode* left;
  8.     SegmentTreeNode* right;
  9.     SegmentTreeNode(int a, int b):start(a),end(b),sum(0),left(nullptr),right(nullptr){}
  10. };
  11.  
  12.  
  13.    
  14. SegmentTreeNode* buildTree(vector<int> &nums, int start, int end) {
  15.     if(start > end) return nullptr;
  16.     SegmentTreeNode* root = new SegmentTreeNode(start,end);
  17.     if(start == end) {
  18.         root->sum = nums[start];
  19.         return root;
  20.     }
  21.     int mid = start + (end - start) / 2;
  22.     root->left = buildTree(nums,start,mid);
  23.     root->right = buildTree(nums,mid+1,end);
  24.     root->sum = min(root->left->sum,root->right->sum);
  25.     return root;
  26. }
  27. int queryTree(int i, int j, SegmentTreeNode* root) {
  28.     if(root == nullptr) return 0;
  29.     if(root->start == i && root->end == j) return root->sum;
  30.     int mid = (root->start + root->end) / 2;
  31.     if(i > mid) return queryTree(i,j,root->right);
  32.     if(j <= mid) return queryTree(i,j,root->left);
  33.     return min(queryTree(i,mid,root->left),queryTree(mid+1,j,root->right));
  34. }
  35. int modifyTree(int i, int val, SegmentTreeNode* root) {
  36.     if(root == nullptr) return 0;
  37.  
  38.     if(root->start == i && root->end == i) {
  39.         root->sum=val;
  40.         return val;
  41.     }
  42.     int mid = (root->start + root->end) / 2;
  43.     if(i > mid) {
  44.         int value=modifyTree(i,val,root->right);
  45.         root->right->sum = min(root->right->sum,value);
  46.     } else {
  47.         int value=modifyTree(i,val,root->left);
  48.         root->left->sum = min(root->left->sum,value);
  49.     }
  50.     root->sum = min(root->right->sum,root->left->sum);
  51.     return root->sum;
  52. }
  53.  
  54. int main()
  55. {
  56.    int q,n,a,t,b;
  57.    cin>>n>>q;
  58.    vector<int>v(n);
  59.    for(int i=0;i<n;i++)cin>>v[i];
  60.    SegmentTreeNode* root=buildTree(v,0,n-1);
  61.    while(q--){
  62.        cin>>t>>a>>b;
  63.        if(t==2)cout<<queryTree(a-1,b-1,root)<<endl;
  64.        else modifyTree(a-1,b,root);
  65.    }
  66.    return 0;
  67. }
RAW Paste Data