[BOJ] #2042 구간 합 구하기

시간 제한	메모리 제한	정답 비율
2 초	256 MB	23.830 %

2042번: 구간 합 구하기

 

문제

 

해결

key point, 세그먼트 트리

2021/02/15 - [🔥 PS(Problem Solving) 🔥/BOJ] - [BOJ] #10868 최솟값

2021/02/15 - [🔥 PS(Problem Solving) 🔥/BOJ] - [BOJ] #11505 구간 곱 구하기

• 위의 두 문제와 방식은 동일하지만 이 문제는 구간의 합을 구하는 문제이다.
• 따라서 구간 곱 구하기 문제와 좀 더 유사하며
• 입력으로 주어지는 모든 수가 long long 범위이기 때문에 전부 long long 처리를 해야만 '맞았습니다.'를 받을 수 있었다.

 

코드

메모리	시간
17616 KB	268 ms

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;
int n, m, k, h = 1;
vector<ll> seg;
void update(ll i, ll num) {
    i += h - 1;
    seg[i] = num;
    while (i > 1) {
        i /= 2;
        seg[i] = seg[i * 2] + seg[i * 2 + 1];
    }
}
// l, r 찾는 범위, num 현재 노드 번호, nl, nr 현재 범위
ll query(ll l, ll r, ll num, ll nl, ll nr) {
    if (l <= nl && nr <= r) return seg[num];
    if (nl > r || nr < l) return 0;
 
    int mid = (nl + nr) / 2;
    return query(l, r, num * 2, nl, mid) + query(l, r, num * 2 + 1, mid + 1, nr);
}
 
int main() {
    scanf("%d%d%d", &n, &m, &k);
    while (h < n) h <<= 1;
    seg.resize(h * 2);
    ll a, b, c;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a);
        update(i + 1, a);
    }
    for (int i = 0; i < m + k; i++) {
        scanf("%lld%lld%lld", &a, &b, &c);
        if (a == 1) update(b, c);
        else printf("%lld\n", query(b, c, 1, 1, h));
    }
    return 0;
}