• Source 
    1. #include <iostream>
    2. #include <cstdio>
    3. using namespace std;
    4. int n,m,N,end,M;
    5. long long tree[500000];
    6. long long a[100002],reva[100002];
    7. void build_tree()
    8. {
    9. 	int i;
    10. 	for(i=1;i<=n;i++)
    11. 		tree[N-(N+1)/2+i]=reva[i];
    12. 	for(i=N-(N+1)/2;i>=1;i--)
    13. 		tree[i]=tree[2*i]+tree[2*i+1];
    14. }
    15. void add_element(long long x)
    16. {
    17. 	n++;
    18. 	end=N-(N+1)/2+n;
    19.  
    20.  
    21. 	while(end!=0)
    22. 	{
    23. 		tree[end]=tree[end]+x;
    24. 		end=end/2;
    25. 	}
    26. }
    27. long long query(int node, int x, int y, int px, int py)
    28. {
    29. 	if(x==px && y==py)
    30. 		return tree[node];
    31. 	int mid=(x+y)/2;
    32. 	if(px>=x && py<=mid)
    33. 		return query(node*2,x,mid,px,py);
    34. 	else
    35. 		if(px>mid && py<=y)
    36. 			return query(node*2+1,mid+1,y,px,py);
    37. 		else
    38. 			return query(node*2,x,mid,px,mid)+query(node*2+1,mid+1,y,mid+1,py);
    39. }
    40. int closest_power()
    41. {
    42. 	int b=1;
    43. 	while(b<n)
    44. 		b=b*2;
    45. 	return b;
    46. }
    47.  
    48. int main()
    49. {
    50. 	int i,j,b,x,y,c,d,e,f,g,t,k;
    51. 	scanf("%d",&n);
    52. 	for(i=1;i<=n;i++)
    53. 	{
    54. 		scanf("%lld",&a[i]);
    55. 		reva[n-i+1]=a[i];
    56. 	}
    57. 	N=1;
    58. 	while(N<=n || N<100000)
    59. 		N=N*2;
    60. 	N=N*4;
    61. 	N--;
    62. 	build_tree();
    63. 	scanf("%d",&t);
    64. 	for(k=1;k<=t;k++)
    65. 	{
    66. 		scanf("%d",&b);
    67. 		if(b==1)
    68. 		{
    69. 			scanf("%d%d",&x,&y);
    70. 			printf("%lld\n",query(1,1,(N+1)/2,n-y+1,n-x+1));
    71. 		}
    72. 		else
    73. 		{
    74. 			scanf("%d",&c);
    75. 			add_element(c);
    76. 		}
    77. 	}
    78. 	return 0;
    79. }
    80.  
    81.