Advertisement
fariahasan

segment tree minimum query

Mar 27th, 2020
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.12 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #define mx 100001
  4.  
  5. int arr[mx], tree[mx*3];
  6. using namespace std;
  7. int query( int node , int b, int e, int i, int j)
  8. {
  9. if(i>e || j<b)
  10. {
  11. return mx;
  12. }
  13. else if(b>=i && e<=j)
  14. {
  15. return tree[node];
  16. }
  17. else
  18. {
  19. int mid=(b+e)/2;
  20. int left =node*2;
  21. int right=node*2+1;
  22. int la=query(left,b,mid,i,j);
  23. int ra=query(right,mid+1,e,i,j);
  24. return min(la,ra);
  25. }
  26. }
  27.  
  28. void init( int node, int b, int e)
  29. {
  30. if(b==e)
  31.  
  32. {
  33. tree[node]=arr[b];
  34.  
  35. return ;
  36. }
  37. int mid=(b+e)/2;
  38. int left=node*2;
  39. int right =node*2+1;
  40. init(left,b,mid);
  41. init(right,mid+1,e);
  42. tree[node]=tree[left]+tree[right];
  43. }
  44.  
  45. int main()
  46. {
  47. int n,i,t,p,j,n1,n2,k;
  48. cin>>t;
  49. for(i=1;i<=t;i++)
  50. {
  51. cin>>n;
  52. cin>>p;
  53. for(k=1;k<=n;k++)
  54. {
  55. cin>>arr[i];
  56. }
  57. init(1,1,n);
  58. for(j=1;j<=p;j++)
  59. { cin>>n1>>n2;
  60. cout<<query(1,1,n,n1,n2)<<endl;
  61. }
  62.  
  63.  
  64. }
  65.  
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement