세그먼트 트리 구간 합 문제 이다.
이때에 update 방식이 두개가 존재하는데, 하나는 해당 인덱스로 찾아가면서 차이를 더 해 주는 것과 바꾸어야 하는 곳의 값을 바꾼후에 다시 더해주면서 올라 오는 방식이다.
둘이 비슷 해 보이지만 ,전자의 경우에는 맨 처음 입력을 받는 배열을 long long 으로 바꾸어야 한다. 그 이유는 차이를 계산할 때에 있어서 그 값이 long long 의 범위에 있을 경우가 있는데 ,이를 위해서 long long 으로 선언 해야 한다.
하지만, 후자의 경우에는 그냥 int 로 선언해되 괜찮다.
1.
2.
#include <cmath>
#include <iostream>
using namespace std;
int N, Q;
long long *tree;
int arr[100001];
long long init(int node, int start, int end) {
if (start == end) return tree[node] = arr[start];
int mid = (start + end) / 2;
return tree[node] = init(node * 2, start, mid) + init(node * 2 + 1, mid + 1, end);
}
long long update(int node, int start, int end, int idx, int val) {
if (idx < start || end < idx) return tree[node];
if (start == end) return tree[node] = val;
int mid = (start + end) / 2;
return tree[node] = update(node * 2, start, mid, idx, val) + update(node * 2 + 1, mid + 1, end, idx, val);
}
long long sumNum(int node, int start, int end, int left, int right) {
if (start > right || end < left) return 0;
if (left <= start && end <= right) return tree[node];
int mid = (start + end) / 2;
return sumNum(node * 2, start, mid, left, right) + sumNum(node * 2 + 1, mid + 1, end, left, right);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> Q;
int height = ceil(log2(N));
tree = new long long[1 << (height + 1)];
for (int i = 1; i <= N; i++) {
cin >> arr[i];
}
init(1, 1, N);
int a, b, x, y;
for (int i = 0; i < Q; i++) {
cin >> x >> y >> a >> b;
int big = max(x, y);
int small = min(x, y);
cout << sumNum(1, 1, N, small, big) << '\n';
update(1, 1, N, a, b);
}
return 0;
}