fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. typedef long long int ll;
  6.  
  7.  
  8. void build(ll a[],ll segtree[],ll n)
  9. {
  10.  
  11. ll i;
  12.  
  13. i=0;
  14. while(i<n)
  15. {
  16.     segtree[n+i]=a[i];
  17.     i++;
  18. }
  19.  
  20. i=n-1;
  21. while(i>=1)
  22. {
  23.     segtree[i]=segtree[2*i]+segtree[2*i+1];   
  24.     i--;
  25. }
  26.  
  27. i=1;
  28. while(i<2*n)
  29. {
  30.  
  31.  
  32.     cout<<segtree[i]<<" ";
  33.  
  34.     i++;
  35. }
  36.  
  37.  
  38.  
  39. }
  40.  
  41.  
  42. void update(ll segtree[],ll index,ll value,ll n)
  43. {
  44.  
  45.  
  46.     index=index+n;
  47.  
  48.     segtree[index]=value; //jahaan__hai___vahaaan___thuso___
  49.  
  50.     while(index>1)
  51.     {
  52.  
  53.  
  54.         index=index/2;
  55.  
  56.      segtree[index] = segtree[2*index] + segtree[2*index+1] ;   
  57.  
  58.     }
  59.   }
  60.  
  61.  
  62.  
  63.  
  64. ll range(ll segtree[],ll left,ll right,ll n)
  65. {
  66.  
  67.      left=left+n; 
  68.     right=right+n; 
  69.  
  70.     ll mi=0;
  71.  
  72.     while(left<right) 
  73.     { 
  74.  
  75.         if(left & 1) 
  76.         { 
  77.  
  78.         mi = (mi + segtree[left]);
  79.             left++; 
  80.         } 
  81.  
  82.  
  83.         if (right & 1)
  84.         { 
  85.  
  86.  
  87.             right--; 
  88.  
  89.             mi = (mi + segtree[right]); 
  90.  
  91.  
  92.         } 
  93.  
  94.  
  95.  
  96.         left /= 2; 
  97.         right /= 2; 
  98.  
  99.  
  100.     } 
  101.  
  102.     return mi; 
  103.  
  104.  
  105. }
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112. int main()
  113. {
  114.     ll n;
  115.     cin>>n;
  116.     ll a[n];
  117.  
  118.     ll i=0;
  119.     while(i<n)
  120.     {
  121.  
  122.         cin>>a[i];
  123.  
  124.  
  125.     i++;
  126.     }
  127.  
  128.     ll segtree[4*n];
  129.  
  130.  
  131.  
  132.     build(a,segtree,n);
  133.  
  134.  
  135.     //--0--based--indexing--when---updating!!!!!
  136.  
  137.  
  138.     update(segtree,4,6,n);
  139.  
  140.     cout<<"\n";
  141.  
  142.     i=1;
  143. while(i<2*n)
  144. {
  145.  
  146.  
  147.     cout<<segtree[i]<<" ";
  148.  
  149.     i++;
  150. }
  151.  
  152.  
  153.  
  154.  ll sex=range(segtree,0,5,n); //it will give sum...from [0,4]..remember that!! always l+1
  155.  
  156.  
  157.  
  158.  cout<<sex<<"\n";
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.     return 0;
  168. }
  169.  
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
5
1 2 3 4 5
stdout
copy 
15 10 5 9 1 2 3 4 5 
16 11 5 10 1 2 3 4 6 16
https://ideone.com/3ngPY1
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!