fork download
copy 
  1.  
  2.  
  3. 			/* POINT UPDATE + RANGE SUM/MIN/MAX QUERIES + ITERATIVE */ 
  4.  
  5.  
  6. using namespace std;
  7. #include <bits/stdc++.h>+
  8.  
  9. struct SegTree{
  10. 	typedef long long ll; 
  11. 	vector<ll> S; ll n,tt; 
  12. 	// pass 't' as {-1,0,1} for {min,sum,max} segtree
  13. 	SegTree(vector<ll> arr,int t){   
  14. 		n=arr.size(); S.assign(2*n,0); tt=-1e18*t;
  15. 		for(int i=0;i<n;i++)  S[n+i]=arr[i];
  16. 		for(int i=n-1;i>0;i--)S[i]=fn(S[i*2],S[i*2+1]);        
  17. 	}
  18. 	void Updt(int p,int v){
  19. 		S[p+n]=v; p+=n;
  20. 		for(int i=p;i>1;i/=2)S[i/2]=fn(S[i],S[i^1]);
  21. 	}
  22. 	ll Kqry(int l,int r){
  23. 		ll res=tt;
  24. 		for(l+=n,r+=n;l<r;l/=2,r/=2){
  25. 			if(l&1)res=fn(res,S[l++]);
  26. 			if(r&1)res=fn(res,S[--r]);
  27. 		}return res;
  28. 	}
  29. 	inline ll fn(ll a,ll b){
  30. 		return(tt==0)?a+b:(tt<0)?max(a,b):min(a,b);
  31. 	}
  32. };
  33. int main(){
  34.     vector<long long> a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
  35.     SegTree S1(a,-1);
  36.     cout<<S1.Kqry(3,6)<<"\n";
  37.     S1.Updt(5,-1);
  38.     cout<<S1.Kqry(3,6)<<"\n";
  39. }
Success #stdin #stdout 0s 4488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
-1
https://ideone.com/EL9FCi
POINT UPDATE + RANGE SUM/MIN/MAX QUERIES + ITERATIVE
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!