bhupixb

Node update range minimum query

Jul 25th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.90 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 1e4;
  4. typedef long long int ll;
  5. ll arr[N], tree[N];
  6.  
  7. void build(int l, int r, int idx){
  8. if(l == r){
  9. tree[idx] = arr[l];
  10. return;
  11. }
  12. ll mid = l + r >> 1;
  13. build(1, mid, 2 * idx);
  14. build(mid + 1, r, 2* idx + 1);
  15.  
  16. tree[idx] = max(tree[2 * idx], tree[2 * idx + 1]);
  17. }
  18. void update(int l, int r, int pos, ll val, int idx){
  19. if(l == r && pos == l){
  20. tree[idx] = val;
  21. arr[l] = val;
  22. return ;
  23. }
  24. if(l > pos || pos > r)return;;
  25.  
  26. ll mid = (l + r) >> 1;
  27.  
  28. update(l, mid, pos, val, 2 * idx);
  29. update(mid + 1, r, pos, val, 2 * idx + 1);
  30. tree[idx] = max(tree[2 * idx], tree[2 * idx + 1]);
  31.  
  32.  
  33. }
  34. //ll query(int l, int r, )
  35. int main(){
  36. int i, n;
  37. cin >> n;
  38. for(i = 1; i <= n; i++)
  39. cin >> arr[i];
  40.  
  41. build(1, n, 1);
  42.  
  43.  
  44. return 0;
  45. }
Add Comment
Please, Sign In to add comment