[백준OJ] 2268번 수들의 합

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

2268번: 수들의 합

---

 

-풀이-

세그먼트트리의 기본적인 문제이다. 하지만 주의해야할점이 sum쿼리를 실행할때 i>j인 경우가 있으므로, 위와 같은 경우라면 i와 j를 swap해주어야한다.

또한 초기값이 모두 0이므로, 세그먼트트리를 초기화해주는 작업을 안해주어도 상관이없었다.

 

-시간복잡도-

sum과 modify 함수 모두 세그먼트트리의 쿼리이기 때문에 O(logN) 시간이 걸린다.

이 동작이 M번 반복되므로, O(MlogN)시간이 걸린다.

 

-코드-

 

#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;

ll tree[4 * 1000000];
ll arr[1000000];
int n,m;

ll init(int node, int st, int end) {
	if (st == end) {
		return tree[node] = arr[st];
	}

	int mid = (st + end) / 2;
	return init(node * 2, st, mid) + init(node * 2 + 1, mid + 1, end);
}

ll sum(int node, int st, int end, int left, int right) {
	if (left <= st && end <= right) {
		return tree[node];
	}
	if (right < st || end < left) {
		return 0;
	}

	int mid = (st + end) / 2;
	return sum(node * 2, st, mid, left, right) + sum(node * 2 + 1, mid + 1, end, left, right);
}

void modify(int node, int st, int end, int ind, long long dif) {
	if (ind < st || end < ind) return;
	tree[node] -= dif;
	
	if (st != end) {
		int mid = (st + end) / 2;
		modify(node * 2, st, mid, ind, dif);
		modify(node * 2 + 1, mid + 1, end, ind, dif);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;


	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 0) {
			if (b > c) {
				int temp = b;
				b = c;
				c = temp;
			}
			cout << sum(1, 0, n - 1, b - 1, c - 1) << "\n";
		}
		else {
			long long diff = arr[b - 1] - c;
			arr[b - 1] = c;
			modify(1, 0, n - 1, b - 1, diff);
		}
	}
	return 0;
}