BOJ 2268, 수들의 합
ProblemSolving ·이 문제는 세그먼트 트리 알고리즘을 이용한 문제이다. 오늘 세그먼트 트리 문제들을 풀어보다가 제일 기본적인 세그먼트 트리의 알고리즘을 잘 보여줄 수 있는 문제같아서 포스팅하기로 하였다!
풀이
세그먼트 트리를 구현하는 방법에는 2가지가 있다.
하나는 트리의 리프노드부터 루트노드까지 올라가면서 구현하는 bottom-up 방식!
나머지 하나는 루트노드부터 리프노드까지 내려가면서 구현하는 top-down 방식!
(개인적으로 Bottom-up 을 선호하여 bottom-up 스타일로 코딩하였다.)
기본 문제임에도 처음에 문제를 틀렸는데 틀린 이유는
a가 0일 때(sum값을 출력할 때) 무조건 b에서 c까지의 합을 출력하는 것이 아니라 c가 더 작으면 c부터 b까지의 합을 출력해야한다.
또 하나 주의해야할 점은 최대값이 int의 범위를 초과한다는 것이다!
그래서 long long형을 사용하였다!
(모든 변수에 long long형을 써야하는 것은 아니지만 불안해서 모두 long long 형을 썼다…)
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
ll h, n, m;
vector<ll> tree;
void update(int idx, ll val)
{
idx += h;
tree[idx] = val;
while (idx /= 2)
tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}
ll query(ll left, ll right)
{
left += h;
right += h;
ll ret = 0;
for (; left < right; left /= 2, right /= 2)
{
if (left % 2)
ret += tree[left++];
if (!(right % 2))
ret += tree[right--];
}
if (left == right)
ret += tree[left];
return ret;
}
int main()
{
cin >> n >> m;
h = (1 << (ll)log2(n - 1) + 1);
tree.resize(h * 2, 0);
for (ll i = 0; i < m; i++)
{
ll a,b,c;
scanf("%lld", &a);
if (a == 0)
{
scanf("%lld %lld", &b, &c);
printf("%lld\n", query(min(c-1,b-1), max(c - 1, b - 1)));
}
if (a == 1)
{
scanf("%lld %lld", &b, &c);
update(b-1,c);
}
}
return 0;
}