[백준] 커피숍2(1275)

문제 링크 : [백준] 커피숍2(1275)

문제 설명

배열 A가 주어지고, 반복적으로 x~y 사이의 합을 출력하고, a번째 값을 b로 바꿉니다.

입력

N(배열의 크기, 1<=N<=100,000)
Q(쿼리 갯수, 1<=Q<=100,000)
D_i(배열의 원소들, D_i는 int 범위)
X_i Y_i A_i B_i(X_i~Y_i까지의 합을 구함, A_i의 값을 B_i으로 바꿈)

5 2
1 2 3 4 5
2 3 3 1
3 5 4 1

출력

5
10

카테고리

#펜윅트리, #세그먼트트리

시간 복잡도 상한

O(NlogN)까지 가능합니다.

해결 방법

1. 반복적인 구간합과 업데이트가 일어나므로 펜윅트리나 세그먼트 트리를 이용하면 됩니다.

시간복잡도

O(NlogN)

코드

#include<iostream>
#define ll long long
using namespace std;
ll e[400004],n,m,a,b,c,f,i,d[100001];
ll j(ll p,ll l,ll r){
    if(l==r)return e[p]=d[l];
    return e[p]=j(p*2,l,(l+r)/2)+j(p*2+1,(l+r)/2+1,r);
}
void u(ll p,ll l,ll r,ll x,ll v){
    if(l>x||r<x)return;
    e[p]+=v;
    if(l!=r)u(p*2,l,(l+r)/2,x,v),u(p*2+1,(l+r)/2+1,r,x,v);
}
ll s(ll p,ll l,ll r,ll x,ll y){
    if(l>y||r<x)return 0;
    if(x<=l&&r<=y)return e[p];
    return s(p*2,l,(l+r)/2,x,y)+s(p*2+1,(l+r)/2+1,r,x,y);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(i=1;i<=n;i++)cin>>d[i];
    j(1,1,n);
    while(m--){
        cin>>a>>b>>c>>f;
        if(a>b)i=a,a=b,b=i;
        cout<<s(1,1,n,a,b)<<"\n";
        u(1,1,n,c,f-d[c]);
        d[c]=f;
    }
}