fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cmath>
  6. #define ll long long
  7. using namespace std;
  8.  
  9. int getmid(int ss,int se)
  10. {
  11.   return ss+(se-ss)/2;
  12. }
  13.  
  14.  
  15. int constructSTUtil(int arr[],int ss,int se,int *st,int si)
  16. {
  17.   if(ss==se)
  18.   {
  19.     st[si]=arr[ss];
  20.     return arr[ss];
  21.   }
  22.   int mid = getmid(ss,se);
  23.   st[si]=constructSTUtil(arr,ss,mid,st,2*si+1)+ constructSTUtil(arr,mid+1,se,st,2*si+2);
  24.   return st[si];
  25. }
  26.  
  27. int *constructST(int arr[],int n)
  28. {
  29.   int x = (int)ceil(log2(n));
  30.   int max_size = 2*pow(2,x)-1;
  31.   int *st = new int[max_size];
  32.   constructSTUtil(arr,0,n-1,st,0);
  33.   return st;
  34. }
  35.  
  36.  
  37. int main()
  38. {
  39.   ios_base::sync_with_stdio(0);
  40.   int n;
  41.   cin >> n;
  42.   int arr[n];
  43.   for(int i=0;i<n;i++)
  44.     cin >> arr[i];
  45.   int *st = constructST(arr,n);
  46.   for(int i=0;i<10;i++)
  47.     cout << st[i] << endl;
  48.   return 0;
  49. }
  50.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
6
1 2 3 4 5 6
stdout
copy 
21
6
15
3
3
9
6
1
2
0
https://ideone.com/xzurlR
language:
C++14 (gcc 8.3)
created:
7 years 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!