Submission

P-PPPPPPPPPPPPPPPPPP

Score: 95

User: Monasm

Problemset: ผลบวก (ยาก)

Language: cpp

Time: 0.077 second

Submitted On: 2024-09-29 16:25:41

#include <bits/stdc++.h>

#define int long long int

using namespace std;

void uconfig(int *segt,int s,int e,int i,int diff,int ni){
    if(i<s||i>e){
        return;
    }
    segt[ni]+=diff;
    if(s!=e){
        int mid = (s+e)/2;
        uconfig(segt,s,mid,i,diff,2*ni+1);
        uconfig(segt,mid+1,e,i,diff,2*ni+2);
    }
}

void update(int arr[],int *segt,int n,int i,int x){
    int diff = x-arr[i];
    arr[i] = x;
    uconfig(segt,0,n-1,i,diff,0);
}

int summation(int *segt,int s,int e,int x,int y,int ni){
    if(y<s||x>e){
        return 0;
    }
    if(x<=s&&e<=y){
        return segt[ni];
    }
    int mid = (s+e)/2;
    return summation(segt,s,mid,x,y,2*ni+1)+summation(segt,mid+1,e,x,y,2*ni+2);
}

int sum(int *segt,int n,int x,int y){
    return summation(segt,0,n-1,x,y,0);
}

int construct(int arr[],int *segt,int si,int ei,int ni){
    if(si == ei){
        segt[ni] = arr[si];
        return segt[ni];
    }
    int mid = (si+ei)/2;
    segt[ni] = construct(arr,segt,si,mid,2*ni+1)+construct(arr,segt,mid+1,ei,2*ni+2);
    return segt[ni];
}

int *segt_con(int arr[],int n){
    int level = ceil(log2(n));
    int size = pow(2,level+1)-1;
    int *segt = new int[size];
    construct(arr,segt,0,n-1,0);
    return segt;
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;cin >> n;
    int arr[n];
    for(auto &i:arr){
        cin >> i;
    }
    int *segt = segt_con(arr,n);
    int q;cin >> q;
    while(q--){
        int t;cin >> t;
        while(t--){
            int x,y;cin >> x >> y;
            update(arr,segt,n,x,y);
        }
        int x,y;cin >> x >> y;
        cout <<sum(segt,n,x,y)<<endl;
    }
    return 0;
}