[ BOJ 백준 1275번 - 커피숍2 ] 해설 및 코드

https://www.acmicpc.net/problem/1275

 

 

목적

N개의 정수 원소가 있는 배열에서 부분 합을 출력하고, 원소를 수정하자.

 

접근법

1. 세그먼트 트리 구현의 기본 예제이다.(참고, 백준 2042 - 구간 합 구하기) 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define fr(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
typedef long long ll;
 
int n,q,offset;
ll t[1<<19]{};
 
void update(int a,int b){
    t[a+=offset]=b;
    while(a>>=1)t[a]=t[a<<1]+t[(a<<1)|1];
}
 
ll query(int x,int y){
    ll ret=0;
    x+=offset;y+=offset;
    while(x<=y){
        if(x&1)ret+=t[x++];
        if(!(y&1))ret+=t[y--];
        x>>=1;y>>=1;
    }
    return ret;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>q;
    
    offset=1;
    while(offset<n)offset<<=1;
    --offset;
    
    f(i,1,n)cin>>t[i+offset];
    fr(i,offset,1)t[i]=t[i<<1]+t[(i<<1)|1];
    
    while(q--){
        int x,y,a,b;cin>>x>>y>>a>>b;
        if(x>y)swap(x,y);
        cout<<query(x, y)<<'\n';
        update(a,b);
    }
    
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.