📝 문제 정보#
🧐 관찰 및 접근#
- 자명한 세그먼트 트리 연습 문제이다.
- 기본적으로 업데이트가 없이 구간의 합을 구해야 한다면, 이는 누적합으로 빠르게 해결할 수 있다.
- 이때 합을 구하는 쿼리는 $O(1)$, 업데이트는 $O(N)$이다.
- 업데이트를 빠르게 하기 위해선, 합을 나이브하게 구하는 방법이 있겠다.
- 이때 합을 구하는 쿼리는 $O(N)$, 업데이트는 $O(1)$이다.
- 버킷을 잘 나누어서, 두 방법의 이득만을 취하면 제곱근 분할법을 이용해서 $O(Q\sqrt{N})$까지 줄일 수 있고, 해당 문제에서는 $N \leq 10^6$이므로 약 2천만정도에 바운드된다.
- 지금과 같이 두 노드를 합치는 것이 직관적이고 용이할 경우에는 세그먼트 트리를 쓸 수 있으며, 두 노드를 이용해 역원과 역연산을 정의할 수 있는 경우 펜윅트리도 이용할 수 있다.
💻 풀이#
- 코드 (C++):
void solve(){
ll N, M, K; cin >> N >> M >> K;
SegmentTreeSum ST(N);
rep(i, 0, N){
ll x; cin >> x;
ST.set(i, x);
}
ST.build();
rep(i, 0, M+K){
ll a, b, c; cin >> a >> b >> c;
if(a == 1) ST.update(b-1, c - ST.query(b-1, b-1));
else cout << ST.query(b-1, c-1) << "\n";
}
}const int sq = 1100;
struct sqrtDecomposition{
int N;
vector<ll> A, bucket;
sqrtDecomposition(int N, vector<ll> &A): N(N), A(A){
bucket.resize((N-1)/sq+1);
rep(i, 0, N) bucket[i/sq] += A[i];
}
void set(int i, ll x){
bucket[i/sq] += x - A[i];
A[i] = x;
}
ll query(int L, int R){
ll ret = 0;
for(int i = L; i <= R;){
if(i%sq == 0 && i+sq-1 <= R){
ret += bucket[i/sq];
i += sq;
}
else{
ret += A[i];
i++;
}
}
return ret;
}
};
void solve(){
ll N, M, K; cin >> N >> M >> K;
vector<ll> a(N);
rep(i, 0, N) cin >> a[i];
sqrtDecomposition SD(N, a);
rep(i, 0, M+K){
ll a, b, c; cin >> a >> b >> c;
if(a == 1) SD.set(b-1, c);
else cout << SD.query(b-1, c-1) << "\n";
}
}