CSES Problem Set Static Range Sum Queries Solution

 Problem Link : https://cses.fi/problemset/task/1646/

Solution in C++:

/// Author : AH_Tonmoy

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 9 ;

using ll = long long ;

ll a[N] ;

ll t[N*4] ;

void build( ll node ,ll b , ll e ) {

if ( b == e ){

t[node] = a[b] ;

return ;

}

ll l = 2 * node , r = 2 * node + 1 ;

ll mid = ( b + e )/2 ;

build( l , b , mid ) ;

build(r , mid + 1 , e) ;

t[node] = t[l] + t[r] ;

}

ll query( ll node , ll b , ll e , ll i , ll j ){

if ( i > e or j < b) return 0 ;

if ( i <= b and e <= j){

return t[node] ;

}

ll l = 2 * node , r = 2 * node + 1 ;

ll mid = ( b + e )/2 ;

return query( l , b , mid , i , j ) + query( r , mid + 1 , e , i , j ) ;

}

void upd( ll node , ll b , ll e , ll i , ll x) {

if ( i < b or i > e ) return ;

if( b == e and b == i ) {

t[node] = x ;

return ;

}

ll l = 2 * node , r = 2 * node + 1 ;

ll mid = ( b + e )/2 ;

upd( l , b , mid , i , x) ;

upd( r , mid + 1 , e , i , x) ;

t[node] = t[l] + t[r] ;

}

int32_t main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

ll n , m ;

cin >> n >> m ;

for ( ll i = 1 ; i <= n ; i++) {

cin >> a[i] ;

}

/// o base tai 0, n - 1 ;

build(1,1,n);

while ( m --) {

ll num , l , r;

cin >> l >> r ;

cout << query(1 , 1 , n , l , r ) <<'\n' ;

}

return 0 ;

}