# segment tree線段樹

## 模板

#pragma GCC optimize("Ofast","inline","-ffast-math","no-stack-protector")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inf 1e9
#define maxn 100005
#define mod 1000000007

int arr[maxn];
int tree[maxn*4];

//建樹
void build(int node,int start,int end){
    if(start==end){
        tree[node]=arr[start];
    }
    else{
        int mid=(start+end)/2;
        int left_node=2*node+1;
        int right_node=2*node+2;

        build(left_node,start,mid);
        build(right_node,mid+1,end);
        tree[node]=tree[left_node]+tree[right_node];
    }
}

//更新樹上的某一點
void update(int node,int start,int end,int idx,int val){
    if(start==end){
        arr[idx]=val;
        tree[node]=val;
    }
    else{
        int mid=(start+end)/2;
        int left_node=2*node+1;
        int right_node=2*node+2;
        if(idx>=start and idx<=mid){
            update(left_node,start,mid,idx,val);
        }
        else{
            update(right_node,mid+1,end,idx,val);   
        }
        tree[node]=tree[left_node]+tree[right_node];
    }
}

//L到R的和
int query(int node,int start,int end,int L,int R){
    if(R<start or L>end){
        return 0;
    }
    else if(start==end){
        return tree[node];
    }
    else{
        int mid=(start+end)/2;
        int left_node=2*node+1;
        int right_node=2*node+2;
        int sum_left=query(left_node,start,mid,L,R);
        int sum_right=query(right_node,mid+1,end,L,R);
        return sum_left+sum_right;
    }
}

signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

}

## 範例練習
CSES:Static Range Sum Queries
https://cses.fi/problemset/task/1646

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define inf 1e9
#define maxn 10000005
 
int arr[maxn];
int tree[maxn];
void build(int node,int start,int end){
    if(start==end){
        tree[node]=arr[start];
    }
    else{
        int mid=(start+end)/2;
        int left_node=2*node+1;
        int right_node=2*node+2;
        build(left_node,start,mid);
        build(right_node,mid+1,end);
        tree[node]=tree[left_node]+tree[right_node];
    }
}
 
int query(int node,int start,int end,int left,int right){
    if(right<start or left>end){
        return 0;
    }
    else if(left<=start and end<=right){
        return tree[node];
    }
    else if(start==end){
        return tree[node];
    }
    else{
        int mid=(start+end)/2;
        int left_node=2*node+1;
        int right_node=2*node+2;
        int sum_left=query(left_node,start,mid,left,right);
        int sum_right=query(right_node,mid+1,end,left,right);
        return sum_left+sum_right;
    }
}
 
void update(int node,int start,int end,int index,int value){
    if(start==end){
        arr[index]=value;
        tree[node]=value;
    }
    else{
        int mid=(start+end)/2;
        int left_node=2*node+1;
        int right_node=2*node+2;
        if(index>=start and index<=mid){
            update(left_node,start,mid,index,value);
        }
        else{
            update(right_node,mid+1,end,index,value);
        }
        tree[node]=tree[left_node]+tree[right_node];
    }
}
 
 
signed main(){
    
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    build(1,1,n);
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        cout<<query(1,1,n,l,r)<<endl;
    }
}