18. 세그먼트 트리

18.md

0.00MB

0. 복습
1. 세그먼트 트리

세그먼트 : 구간이라는 뜻.

2042번을 보면
방법 1 : for문 -> 업뎃은 빠르지만 쿼리가 느림
방법 2 : 누적합 -> 쿼리는 빠르지만 업뎃은 느림
정답 : 세그먼트 -> 쿼리도 빠르고 업뎃도 빠름

#include <iostream>
using namespace std;
typedef long long int ll;
const int MN = 1000000;
int N, M, K;
ll seg[MN*4+1];

ll Update(int idx, ll val, int n, int l, int r) {
    if(r<idx || idx<l) return seg[n];
    if(l==r) return seg[n] = val;
    int mid = (l+r)/2;
    return seg[n] = Update(idx, val, n*2, l, mid) + Update(idx, val, n*2+1, mid+1, r);
}

ll Query(int L, int R, int n, int l, int r) {
    if (r<L || R<l) return 0;
    if(L<=l && r<=R) return seg[n];
    int mid = (l+r)/2;
    return Query(L, R, n*2, l, mid) + Query(L, R, n*2+1, mid+1, r);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> K;
    for(int i=1; i<=N; ++i){
        ll a;
        cin >> a;
        Update(i, a, 1, 1, N);
    }
    for(int i=0; i<M+K; ++i){
        int c;
        cin >> c;
        if(c==1){
            int x; ll y; cin >> x >> y;
            Update(x, y, 1, 1, N);
        }
        else {
            int x, y; cin >> x >> y;
            cout << Query(x, y, 1, 1, N) << '\n';
        }
    }
}

기본적으로 분할->정복 알고리즘을 사용한다.

참고 : 2042, 2268, 10868, 14438, 2357, 11505, 1517, 10090, 2517