https://www.acmicpc.net/problem/2042
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
// 전체 데이터의 개수는 최대 1,000,000개
long long arr[1000001], tree[1000001];
// 데이터의 개수(n), 변경 횟수(m), 구간 합 계산 횟수(k)
int n, m, k;
// i번째 수까지의 누적합을 계산하는 함수
long long prefixSum(int i)
{
long long result = 0;
while (i > 0) {
result += tree[i];
// 0이 아닌 마지막 비트만큼 빼가면서 이동
i -= (i & -i);
}
return result;
}
void update(int i, long long dif)
{
while (i <= n) {
tree[i] += dif;
i += (i & -i);
}
}
long long intervalSum(int start, int end)
{
return prefixSum(end) - prefixSum(start - 1);
}
int main()
{
int i;
cin >> n >> m >> k;
for (i = 1; i <= n; i++) {
long long x;
cin >> x;
arr[i] = x;
update(i, x);
}
int count = 0;
while (count++ < m + k) {
int op;
cin >> op;
// update
if (op == 1) {
int index;
long long v;
cin >> index >> v;
update(index, v - arr[index]);
arr[index] = v; // i번째 수를 value로 업데이트
}
// interval sum
else {
int start, end;
cin >> start >> end;
cout << intervalSum(start, end) << endl;
}
}
return 0;
}

'Algorithm Study > 백준' 카테고리의 다른 글
| [C++] 백준 18352번 특정 거리의 도시 찾기 (0) | 2023.07.06 |
|---|---|
| [C++] LIS & DP / 백준 11053번 - 가장 긴 증가하는 부분 수열 (0) | 2023.06.15 |
| [C++] Dijkstra algorithm / 백준 1504번 - 특정한 최단 경로 (0) | 2023.06.14 |
| [C++] Dijkstra algorithm - 백준 1238번 파티 (1) | 2023.06.14 |