득이공간
[백준 C++] 2042 구간 합 구하기 - 세그먼트트리 본문
#include <iostream>
#include <cmath>
using namespace std;
int Count, StartIndex;
long long SegmentTree[1048576 * 2];
void UpdateTree(int N, int Index, long long Value)
{
int Current = StartIndex + Index;
SegmentTree[Current] = Value;
for (int i = Current / 2; i > 0; i /= 2)
{
SegmentTree[i] = SegmentTree[2 * i] + SegmentTree[2 * i + 1];
}
}
void PrintSum(int N, int Start, int End)
{
int CurStart = StartIndex + Start;
int CurEnd = StartIndex + End;
long long Sum = 0;
while (CurStart <= CurEnd)
{
if (CurStart % 2 == 1)
{
Sum += SegmentTree[CurStart];
}
if (CurEnd % 2 == 0)
{
Sum += SegmentTree[CurEnd];
}
CurStart = (CurStart + 1) / 2;
CurEnd = (CurEnd - 1) / 2;
}
cout << Sum << '\n';
}
void InitTree(int N)
{
while (pow(2, Count) < N)
{
++Count;
}
StartIndex = pow(2, Count);
for (int i = StartIndex; i < StartIndex + N; ++i)
{
cin >> SegmentTree[i];
}
for (int i = StartIndex - 1; i > 0; --i)
{
SegmentTree[i] = SegmentTree[2 * i] + SegmentTree[2 * i + 1];
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N, M, K;
cin >> N >> M >> K;
InitTree(N);
for (int i = 0; i < M + K; ++i)
{
long long A, B, C;
cin >> A >> B >> C;
if (A == 1)
{
UpdateTree(N, B - 1, C);
}
else if (A == 2)
{
PrintSum(N, B - 1, C - 1);
}
}
}
주어진 데이터 배열을 업데이트하거나, 구간합을 구하는 연산을 '빠르게 여러번' 수행할 수 있도록 하는
세그먼트 트리를 이용해서 푸는 가장 대표적인 문제입니다.
주의할 점은 배열의 크기를 조건(2^k >= N)에 맞는 2^k의 최소값에 2를 곱한 만큼 지정해주는 것입니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 10868 최솟값 - 세그먼트트리 (1) | 2024.02.12 |
---|---|
[백준 C++] 2357 최솟값과 최댓값 - 세그먼트트리 (0) | 2024.02.12 |
[백준 C++] 1991 트리 순회 - 이진트리 (0) | 2024.02.10 |
[백준 C++] 1946 신입 사원 - 정렬 (0) | 2024.02.09 |
[백준 C++] 18870 좌표 압축 - 정렬 (0) | 2024.02.09 |