Advertisement
Farjana_akter

Untitled

Nov 25th, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.86 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. long long int arr[1000006],tree[1000006];
  6.  
  7.  
  8. void treebuild(ll node,ll start,ll e)
  9. {
  10. if(start==e)
  11. {
  12. tree[node]=arr[e];
  13. return;
  14. }
  15. ll left=node*2;
  16. ll right=left+1;
  17. ll mid=(start+e)/2;
  18. treebuild(left,start,mid);
  19. treebuild(right,mid+1,e);
  20. tree[node]=tree[left]+tree[right];
  21. }
  22.  
  23.  
  24. void update(ll node,ll start,ll e,ll index,ll value)
  25. {
  26. if(index>e || index<start)
  27. return;
  28. if(start==e)
  29. {
  30. tree[node]=value;
  31. return;
  32. }
  33. ll left=node*2;
  34. ll right=left+1;
  35. ll mid=(start+e)/2;
  36. update(left,start,mid,index,value);
  37. update(right,mid+1,e,index,value);
  38. tree[node]=tree[left]+tree[right];
  39. }
  40.  
  41. ll query(ll node,ll start,ll e,ll ranges,ll rangef)
  42. {
  43. if(ranges>e || rangef<start)
  44. return 0;
  45. if(start>=ranges &&rangef>=e)
  46. return tree[node];
  47. ll left=node*2;
  48. ll right=left+1;
  49. ll mid=(start+e)/2;
  50. ll ans1=query(left,start,mid,ranges,rangef);
  51. ll ans2=query(right,mid+1,e,ranges,rangef);
  52. return ans1+ans2;
  53. }
  54.  
  55. int main()
  56. {
  57. ll n,i,j,test=0,q,ans,index,value,ranges,rangef;
  58. string s;
  59. while(cin>>n && n)
  60. {
  61. for(i=1;i<=n;i++)
  62. cin>>arr[i];
  63. treebuild(1,1,n);
  64. if(test)cout<<endl;
  65. cout<<"Case "<<++test<<":"<<endl;
  66. while(cin>>s)
  67. {
  68. if(s=="END")
  69. break;
  70. else if(s[0]=='S')
  71. {
  72. cin>>index>>value;
  73. arr[index]=value;
  74. update(1,1,n,index,value);
  75. }
  76. else
  77. {
  78. cin>>ranges>>rangef;
  79. ans=query(1,1,n,ranges,rangef);
  80. cout<<ans<<endl;
  81. }
  82. }
  83. }
  84. return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement