fork(4) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX=500020;
  5.  
  6. int tree[MAX];
  7. int A[100005];
  8.  
  9. void Build_Tree(int node, int st, int end)
  10. {
  11. 	if(st == end)
  12. 	{
  13. 		tree[node] = A[st];
  14. 		return ;
  15. 	}
  16. 	int mid = (st+end)/2;
  17. 	Build_Tree(node*2, st, mid);
  18.  
  19. 	Build_Tree(node*2+1, mid+1, end);
  20.  
  21. 	tree[node] = tree[2*node] + tree[2*node+1];
  22. 	return;
  23. }
  24.  
  25. void update(int node, int st, int end, int idx, int value)
  26. {
  27. 	if(st == end)
  28. 	{  
  29. 		tree[node] = value; 
  30. 		tree[node] = value; 
  31. 		A[idx] = value;
  32. 		return ;
  33. 	}
  34.  
  35. 	int mid = (st+end)/2;
  36. 	if(idx<=mid)
  37. 	{
  38. 		update(2*node, st, mid, idx, value);
  39. 	}
  40. 	else
  41. 	{
  42. 		update(2*node+1, mid+1, end, idx, value);
  43. 	}
  44.  
  45. 	tree[node] = tree[2*node] + tree[2*node+1];  
  46. 	return ;
  47. }
  48.  
  49. int RangeSum(int node, int st, int end, int l, int r)
  50. {
  51. 	if(l <= st && end <= r )
  52. 	{
  53. 		return tree[node];
  54. 	}
  55.  
  56. 	if(st>r || end<l)
  57. 		return 0;
  58.  
  59. 	int mid = (st+end)/2;
  60.  
  61. 	int ans1 = RangeSum(2*node, st, mid, l, r);
  62. 	int ans2 = RangeSum(2*node+1, mid+1, end, l, r);	
  63. 	return ans1 + ans2;	
  64. }
  65.  
  66. int main()
  67. {
  68. 	int n,q,l,r,a;
  69. 	cin>>n>>q;
  70. 	for(int i=0;i<MAX;i++)
  71. 		tree[i]=0;
  72. 	for(int i=1;i<=n;i++) {
  73. 		cin>>A[i];
  74. 	}
  75. 	Build_Tree(1,1,n);
  76.  
  77. 	while(q--)
  78. 	{
  79. 		cin>>a>>l>>r;
  80. 		if(a==0)
  81. 		{
  82. 			cout<<RangeSum(1,1,n,l,r)<<endl;
  83. 		}
  84. 		else
  85. 		{
  86. 			update(1,1,n,l,r);
  87. 		}
  88. 	}
  89. 	return 0;
  90. }
Success #stdin #stdout 0s 5516KB
comments (?)
stdin
copy 
10 5
2 8 1 3 7 6 8 1 0 7
0 3 5
1 3 7
0 2 6
1 10 0
0 9 10
stdout
copy 
11
31
0
https://ideone.com/ZzszM7
language:
C++ (gcc 8.3)
created:
4 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!