fork(2) 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. Vertex * update(Vertex * root, int tl, int tr, int idx, int v){
  47. 	if( tl == tr ){
  48. 		assert(tl == idx);
  49. 		return new Vertex(v);
  50. 	}
  51. 	if( idx <= (tl+tr)/2 )
  52. 		return new Vertex( update(root->l, tl, (tl+tr)/2, idx, v), root->r);
  53. 	else
  54. 		return new Vertex( root->l, update(root->r, (tl+tr)/2+1, tr, idx, v));
  55. }
  56.  
  57. int query( Vertex * root, int tl, int tr, int l, int r){
  58. 	if( tl > r || tr < l )
  59. 		return 0;
  60. 	if( tl >= l && tr <= r )
  61. 		return root->val;
  62. 	return query(root->l, tl, (tl+tr)/2, l, r) + query(root->r, (tl+tr)/2+1, tr, l, r);
  63. }
  64.  
  65. int main(){
  66. 	optimizeIO();
  67. 	int n, q, a, b, c, d;
  68. 	cin >> n;
  69. 	REP(i, 0, n)
  70. 		cin >> arr[i];
  71. 	seg.push_back(build(0, n-1));
  72. 	cin >> q;	
  73. 	REP(i, 0, q){
  74. 		cin >> a >> b >> c >> d;
  75. 		if( a == 1 ){
  76. 			seg.push_back( update(seg[b], 0, n-1, c-1, d));
  77. 		}else{
  78. 			cout << query(seg[b], 0, n-1, c-1, d-1) << endl;
  79. 		}
  80. 	}
  81.  
  82. 	return 0;
  83. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
10
1 2 3 4 5 6 7 8 9 10 
5
2 0 1 6
1 0 10 30
1 1 2 10
1 2 3 10
2 3 2 3
stdout
copy 
21
20
https://ideone.com/pegLh2
Implementing Persistance Segment Tree
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!