Dynamic Range Minimum Queries

#include <algorithm>
#include <iostream>
#include <limits>


#include <vector>
struct SegmentTree{
  std::vector<int> tree;
  std::vector<int>& arr;
  int size;
  SegmentTree(std::vector<int>& arr):arr(arr){
    size = arr.size();
    tree.resize(4*size);
    buildTree(0, 0, size-1, arr);
  }

  void buildTree(int treeIndex, int rangeL, int rangeR, std::vector<int>& arr){
    if (rangeL==rangeR){
      tree[treeIndex] = arr[rangeL];
      return;
    }

    int mid = rangeL + (rangeR - rangeL)/2;
    int treeLeftIdx = getLeft(treeIndex);
    int treeRightIdx = getRight(treeIndex);
    buildTree(treeLeftIdx, rangeL, mid, arr);
    buildTree(treeRightIdx, mid+1, rangeR, arr);

    tree[treeIndex] = operation(tree[treeLeftIdx], tree[treeRightIdx]);
  }

  int getLeft(int idx){
    return 2*idx+1;
  }

  int getRight(int idx){
    return 2*idx+2;
  }
  
  int innerQuery(int treeIndex, int ql, int qr, int rangeL, int rangeR){
    if (ql <= rangeL && qr >= rangeR){
      return tree[treeIndex];
    }

    int mid = rangeL + (rangeR - rangeL)/2;
    int treeLeftIdx = getLeft(treeIndex);
    int treeRightIdx = getRight(treeIndex);

    int acc = identity();

    if (ql<=mid){
      acc = operation(acc, innerQuery(treeLeftIdx, ql, qr, rangeL, mid));
    }
    if (qr>mid){
      acc = operation(acc, innerQuery(treeRightIdx, ql, qr, mid+1, rangeR));
    }

    return acc;
  }

  void innerUpdate(int treeIndex, int idx, int val, int rangeL, int rangeR){
    if (idx < rangeL || idx > rangeR){
      return;
    }
    
    if (rangeL==rangeR){
      tree[treeIndex] = val;
      return;
    }


    int mid = rangeL + (rangeR - rangeL)/2;
    int treeLeftIdx = getLeft(treeIndex);
    int treeRightIdx = getRight(treeIndex);
    
    if (idx <= mid){
      innerUpdate(treeLeftIdx, idx, val, rangeL, mid);
    }else {
      innerUpdate(treeRightIdx, idx, val, mid+1, rangeR);
    }
    
    tree[treeIndex] = operation(tree[treeRightIdx], tree[treeLeftIdx]);


  }

  int query(int ql, int qr){
    return innerQuery(0, ql, qr, 0, size-1);
  }


  void update(int idx, int val){
    innerUpdate(0, idx, val, 0, size-1);
    arr[idx] = val;
  }

private:
  int operation(int a, int b){
    return std::min(a, b);
  }

  int identity(){
    return std::numeric_limits<int>::max();
  }
};


struct Query{
  int inst, arg1, arg2;
};


int main(){
  int n, m;
  std::cin >> n >> m;
  std::vector<int> vals(n);
  for (int i = 0; i<n; ++i){
    std::cin >> vals[i];
  }
  SegmentTree st(vals);
  
  std::vector<Query> queries(m);
  for (int q = 0; q<m; ++q){
    int a,b,c;
    std::cin >> a >> b >> c;

    queries[q].inst = a;
    
    if (a==1){
      queries[q].arg1 = b-1;
      queries[q].arg2 = c;
    } else {
      queries[q].arg1 = b-1;
      queries[q].arg2 = c-1;
    }
  }

  for (int q = 0; q<m; ++q){
    if (queries[q].inst == 2){
      int sum = st.query(queries[q].arg1, queries[q].arg2);
      std::cout << sum << "\n";
    }else {
      st.update(queries[q].arg1, queries[q].arg2);
    }
  }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED