백준 11659 구간 합 구하기4

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

11659번: 구간 합 구하기 4

1. 누적 합 알고리즘을 이용한다면 매우 쉬운 문제였습니다

#include <iostream>
#define fastio() ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr);
using namespace std;
int n, m, t1, t2;
int arr[111111];
int acc[111111];
int main() {
    fastio();
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 1; i <= n; i++) acc[i] = acc[i - 1] + arr[i];
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2;
        cout << acc[t2] - acc[t1 - 1] << "\n";
    }
}

 

풀이:

 

arr	1	4	5	10	2	3	8	1	2
acc	1	5	10	20	22	25	33	34	36

acc에 1부터 idx까지 누적 합을 저장해 줍니다.

이를 이용하면 쉽게 풀 수 있습니다.

 

 

 

 

 

---

2. 세그먼트 트리로도 풀 수 있습니다

#include <iostream>
#include <math.h>
#define fastio() ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr);
using namespace std;
typedef long long ll;
ll n, m, k, from;
ll arr[10000000];
void update(ll location, ll v) {
    ll idx = location + from - 1;
    arr[idx] = v;
    for (ll i = idx / 2; i >= 1; i /= 2) {
        arr[i] = arr[i * 2] + arr[i * 2 + 1];
    }
}
ll sum(ll l, ll r, ll idx = 1, ll L = 1, ll R = from) {
    if (l > R or r < L) return 0;
    else if (l <= L and r >= R) return arr[idx];
    ll m = (L + R) / 2;
    return sum(l, r, idx * 2, L, m) + sum(l, r, idx * 2 + 1, m + 1, R);
}
 
int main() {
    fastio();
    cin >> n >> m;
    from = ((n & (n - 1)) == 0) ? pow(2, (int)log2(n)) : pow(2, (int)log2(n) + 1);
    for (ll i = from; i < from + n; i++) cin >> arr[i];
    for (ll i = from - 1; i >= 1; --i) arr[i] = arr[i * 2] + arr[i * 2 + 1];
    for (ll i = 0; i < m + k; i++) {
        ll a, b;
        cin >> a >> b;
        cout << sum(a, b) << "\n";
    }
}

풀이:

https://wantchicken.tistory.com/46

세그먼트 트리의 개념 - c++