fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int a[1000001];
  5. int st[4000001];
  6. int n,k;
  7. void build(int id,int l,int r)
  8. {
  9.     if (l==r)
  10.     {
  11.         st[id]=a[l]; // fixed the index here
  12.     }
  13.     else
  14.     {
  15.         int mid=(l+r) >> 1;
  16.         build(id*2,l,mid);
  17.         build(id*2+1,mid+1,r);
  18.         st[id]=st[id*2]+st[id*2+1];
  19.     }
  20. }
  21. int get(int id,int l,int r,int u,int v)
  22. {
  23.     if (u > r || v < l) return 0;
  24.     if (l >= u && r <= v) return st[id]; // changed l > u to l >= u
  25.     int mid =( l + r ) / 2;
  26.     int dp1 = get(id*2,l,mid,u,v);
  27.     int dp2 = get(id*2+1,mid+1,r,u,v); // fixed the index here
  28.     return dp1 + dp2;
  29. }
  30. signed main()
  31. {
  32.     ios_base::sync_with_stdio(0);
  33.     cin.tie(0);cout.tie(0);
  34.     cin>>n>>k;
  35.     for (int i=1;i<=n;i++)
  36.     {
  37.         cin>>a[i];
  38.     }
  39.     build(1,1,n);
  40.     while (k--)
  41.     {
  42.         int u,v;
  43.         cin>>u>>v;
  44.         cout<<get(1,1,n,u,v)<<"\n";
  45.     }
  46. }
  47.  
Success #stdin #stdout 0.01s 5708KB
comments (?)
stdin
copy 
8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3
stdout
copy 
11
2
24
4
https://ideone.com/aYll2J
language:
C++14 (clang 8.0)
created:
260 days 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!