알고리즘 문제풀이
[백준/BOJ] 백준 10999번 : 구간 합 구하기 2
GeniusJo
2022. 8. 14. 01:53
https://www.acmicpc.net/problem/10999
10999번: 구간 합 구하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
구간 업데이트의 효율을 위해 느리게 갱신되는 세그먼트 트리를 이용해 문제를 해결했다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//구간 업데이트의 효율을 위해 느리게 갱신되는 세그먼트 트리 이용
int n, m, k;
vector<long long> inputs;
vector<long long> sgmtt(4000000, 0);
vector<long long> lazy_check(4000000, 0); //해당 노드에서 갱신해야될 정보 저장
long long MakeSgmtt(int here, int range_left, int range_right)
{
if (range_left == range_right)
return sgmtt[here] = inputs[range_left];
int left_child = here * 2 + 1;
int right_child = here * 2 + 2;
int range_mid = (range_left + range_right) / 2;
return sgmtt[here] = MakeSgmtt(left_child, range_left, range_mid) + MakeSgmtt(right_child, range_mid + 1, range_right);
}
long long QuerySgmtt(int here, int range_left, int range_right, int find_left, int find_right)
{
int left_child = here * 2 + 1;
int right_child = here * 2 + 2;
int range_mid = (range_left + range_right) / 2;
//현재 위치에서 갱신해야 될것이 있을때
if (lazy_check[here] != 0)
{
//현재 위치 갱신
sgmtt[here] += (lazy_check[here] * (range_right - range_left + 1));
//현재 노드가 리프노드가 아닐때, 자식 노드로 갱신 정보를 전달한다
if (range_left != range_right)
{
lazy_check[left_child] += lazy_check[here];
lazy_check[right_child] += lazy_check[here];
}
lazy_check[here] = 0;
}
if (find_right < range_left || range_right < find_left)
return 0;
if (find_left <= range_left && range_right <= find_right)
return sgmtt[here];
return QuerySgmtt(left_child, range_left, range_mid, find_left, find_right) + QuerySgmtt(right_child, range_mid + 1, range_right, find_left, find_right);
}
long long UpdateSgmtt(int here, int range_left, int range_right, int update_left, int update_right, long long add_value)
{
int left_child = here * 2 + 1;
int right_child = here * 2 + 2;
int range_mid = (range_left + range_right) / 2;
//현재 위치에서 갱신해야 될것이 있을때
if (lazy_check[here] != 0)
{
sgmtt[here] += (lazy_check[here] * (range_right - range_left + 1));
//현재 노드가 리프노드가 아닐때, 자식 노드로 갱신 정보를 전달한다
if (range_left != range_right)
{
lazy_check[left_child] += lazy_check[here];
lazy_check[right_child] += lazy_check[here];
}
lazy_check[here] = 0;
}
//현재 범위가 업데이트 하는 범위와 상관 없을때
if (update_right < range_left || range_right < update_left)
return sgmtt[here];
//현재 범위가 업데이트 하는 범위에 속할때
if (update_left <= range_left && range_right <= update_right)
{
//현재 위치 갱신
sgmtt[here] += (add_value * (range_right - range_left + 1));
//현재 노드가 리프노드가 아닐때
if (range_left != range_right)
{
//자식 노드에 갱신할 정보를 저장해 놓는다
lazy_check[left_child] += add_value;
lazy_check[right_child] += add_value;
}
return sgmtt[here];
}
return sgmtt[here] = UpdateSgmtt(left_child, range_left, range_mid, update_left, update_right, add_value) + UpdateSgmtt(right_child, range_mid + 1, range_right, update_left, update_right, add_value);
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
{
long long input;
cin >> input;
inputs.push_back(input);
}
MakeSgmtt(0, 0, n - 1);
for (int i = 0; i < m + k; i++)
{
int a, b, c;
long long d;
cin >> a;
if (a == 1)
{
cin >> b >> c >> d;
UpdateSgmtt(0, 0, n - 1, b - 1, c - 1, d);
}
else
{
cin >> b >> c;
cout << QuerySgmtt(0, 0, n - 1, b - 1, c - 1) << "\n";
}
}
return 0;
}