fork download
copy 
  1. // 
  2. // Created By - Shiv Shankar
  3. //
  4. // https://w...content-available-to-author-only...j.com/problems/PSEGTREE/
  5.  
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. #define REP(i, a, b) for(int i = a; i < b; i++)
  11. #define RREP(i, a, b) for(int i = a-1; i >= b; i--)
  12. #define PB push_back
  13. #define MP make_pair
  14. #define MOD 1000000007
  15. #define INF 0x7fffffff
  16. #define MAX 100005
  17.  
  18. typedef long long ll;
  19. typedef pair< int, int > PII;
  20.  
  21. void optimizeIO(){
  22. 	ios_base::sync_with_stdio(false); 
  23.     cin.tie(NULL);
  24. }
  25.  
  26. struct Vertex{
  27. 	Vertex *l, *r;
  28. 	int val;
  29. 	Vertex(int v): l(nullptr), r(nullptr), val(v){}
  30. 	Vertex(Vertex * a, Vertex * b): l(a), r(b), val(0){
  31. 		if( l ) val += a->val;
  32. 		if( r ) val += b->val;
  33. 	}
  34. };
  35.  
  36. vector< Vertex * > seg;
  37. vector< int > arr(MAX);
  38.  
  39.  
  40. Vertex * build(int tl, int tr){
  41. 	if( tl == tr )
  42. 		return new Vertex(arr[tl]);
  43. 	return new Vertex( build(tl, (tl+tr)/2), build((tl+tr)/2+1, tr));
  44. }
  45.  
  46. int last,nn; 
  47.  
  48. int query( Vertex * root, int tl, int tr, int l, int r){
  49. 	if( tl > r || tr < l )
  50. 		return 0;
  51. 	if( tl >= l && tr <= r )
  52. 		return root->val;
  53. 	return query(root->l, tl, (tl+tr)/2, l, r) + query(root->r, (tl+tr)/2+1, tr, l, r);
  54. }
  55.  
  56. Vertex * update(Vertex * root, int tl, int tr, int idx, int v){
  57. 	if( tl == tr ){
  58. 		assert(tl == idx);
  59. 		return new Vertex(v+query(seg[last], 0, nn-1, idx, idx));
  60. 	}
  61. 	if( idx <= (tl+tr)/2 )
  62. 		return new Vertex( update(root->l, tl, (tl+tr)/2, idx, v), root->r);
  63. 	else
  64. 		return new Vertex( root->l, update(root->r, (tl+tr)/2+1, tr, idx, v));
  65. }
  66.  
  67. int main(){
  68. 	optimizeIO();
  69. 	int n, q, a, b, c, d;
  70. 	cin >> n;
  71. 	nn = n;
  72. 	REP(i, 0, n)
  73. 		cin >> arr[i];
  74. 	seg.push_back(build(0, n-1));
  75. 	cin >> q;	
  76. 	REP(i, 0, q){
  77. 		cin >> a >> b >> c >> d;
  78. 		last = b;
  79. 		if( a == 1 ){
  80. 			seg.push_back( update(seg[b], 0, n-1, c-1, d));
  81. 		}else{
  82. 			cout << query(seg[b], 0, n-1, c-1, d-1) << endl;
  83. 		}
  84. 	}
  85.  
  86. 	return 0;
  87. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KQ3xQ2
problem PSEGTREE, based on SPOJ submission 22923253 (CPP14), 2018-12-22 09:50:35
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!