fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define endl "\n"
  5.  
  6. /*
  7. node:
  8. value
  9. left, right --> what is the range i am responsible for
  10. index -> actual index in linearized vector
  11. root is 0
  12. index of left = 2*node + 1
  13. index of right = 2*node + 2
  14.  
  15. l, r = 0 3 Exactly match
  16. 				41
  17. 	   21                  20
  18.   6         15        16        4
  19. 1   5    3    12    7    9    0    4
  20. size array --> power of 2
  21. fill array = neutral value
  22.  
  23. Data members:
  24. sz
  25. seg vector
  26. Linearization
  27. member functions:
  28. build
  29. update
  30. query
  31. */
  32.  
  33. class segmentTree
  34. {
  35. #define mid (left + right) / 2
  36. #define leftNode 2 * node + 1
  37. #define rightNode 2 * node + 2
  38. private:
  39. 	int sz; // power of 2
  40. 	vector<ll> seg;
  41. 	void build(int left, int right, int node, const vector<ll> &arr)
  42. 	{
  43. 		if (left == right) // leaf node
  44. 		{
  45. 			if (left < arr.size())
  46. 				seg[node] = arr[left];
  47. 			return;
  48. 		}
  49. 		// Left segment
  50. 		build(left, mid, leftNode, arr);
  51. 		// Right segment
  52. 		build(mid + 1, right, rightNode, arr);
  53. 		seg[node] = seg[leftNode] + seg[rightNode];
  54. 	}
  55. 	void update(int left, int right, int node, int idx, ll val)
  56. 	{
  57. 		if (left == right) // leaf node
  58. 		{
  59. 			seg[node] += val;
  60. 			return;
  61. 		}
  62. 		if (idx <= mid)
  63. 			update(left, mid, leftNode, idx, val);
  64. 		else
  65. 			update(mid + 1, right, rightNode, idx, val);
  66. 		seg[node] = seg[leftNode] + seg[rightNode];
  67. 	}
  68. 	ll query(int left, int right, int node, int leftQuery, int rightQuery)
  69. 	{
  70. 		if (right < leftQuery || left > rightQuery)
  71. 			return 0; // neutral value
  72. 		if (left >= leftQuery && right <= rightQuery)
  73. 			return seg[node];
  74. 		ll leftQ = query(left, mid, leftNode, leftQuery, rightQuery);
  75. 		ll rightQ = query(mid + 1, right, rightNode, leftQuery, rightQuery);
  76. 		return leftQ + rightQ;
  77. 	}
  78.  
  79. public:
  80. 	// Interface
  81. 	// Constructor
  82. 	segmentTree(const vector<ll> &arr)
  83. 	{
  84. 		int n = arr.size(); // 25
  85. 		sz = 1;
  86. 		while (sz < n)
  87. 			sz <<= 1;
  88. 		seg.resize(sz, 0); // Neutral
  89. 		build(0, sz - 1, 0, arr);
  90. 	}
  91. 	void update(int idx, ll val)
  92. 	{
  93. 		update(0, sz - 1, 0, idx, val);
  94. 	}
  95. 	ll query(int left, int right)
  96. 	{
  97. 		return query(0, sz - 1, 0, left, right);
  98. 	}
  99. };
  100. int main()
  101. {
  102. 	ios_base::sync_with_stdio(false);
  103. 	cin.tie(nullptr);
  104. #ifndef ONLINE_JUDGE
  105. 	freopen("input.txt", "r", stdin);
  106. 	freopen("Output.txt", "w", stdout);
  107. #endif //! ONLINE_JUDGE
  108. 	int t = 1;
  109. 	ll N;
  110. 	// cin >> t;
  111. 	while (t--)
  112. 	{
  113. 		cin >> N;
  114. 		vector<ll> vc(N);
  115. 		for (int i{}; i < N; i++)
  116. 			cin >> vc[i];
  117. 		segmentTree segTree(vc);
  118. 		int Q;
  119. 		cin >> Q;
  120. 		while (Q--)
  121. 		{
  122.  
  123. 			int q, left, right;
  124. 			cin >> q;
  125. 			if (q == 1)
  126. 			{
  127. 				int idx, val;
  128. 				cin >> idx >> val;
  129. 				segTree.update(idx, val);
  130. 			}
  131. 			else
  132. 			{
  133. 				cin >> left >> right;
  134. 				cout << segTree.query(left, right) << endl;
  135. 			}
  136. 		}
  137. 	}
  138. 	return 0;
  139. }
Success #stdin #stdout #stderr 0.31s 40124KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "using namespace"
Execution halted
https://ideone.com/XuaGYM
language:
R (R 3.5.2)
created:
12 days ago
visibility:
public

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!