백준 10999 - 구간 합 구하기 2(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10999

 

느리게 갱신되는 세그먼트 트리를 이용한 문제입니다.

느리게 갱신되는 세그먼트 트리는 해당 링크를 참조해주세요.  https://www.acmicpc.net/blog/view/26

 

느리게 갱신되는 세그먼트 트리를 사용할 수 있다면 바로 구할 수 있는 문제였습니다.

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

int N, M, K;
long long Index[1000001];
vector<long long> Tree;
vector<long long> lazy;

long long segment_tree(int num, int st, int fin) {
	if (st == fin) return Tree[num] = Index[st];
	int mid = (st + fin) / 2;
	long long left = segment_tree(num * 2, st, mid);
	long long right = segment_tree(num * 2 + 1, mid + 1, fin);
	return Tree[num] = (left + right);
}

void update_lazy(int num, int left, int right) {
	if (lazy[num]) {
		Tree[num] += (lazy[num] * (right - left + 1));
		if (left != right) {
			lazy[num * 2] += lazy[num];
			lazy[num * 2 + 1] += lazy[num];
		}
		lazy[num] = 0;
	}
}

void change_Tree(int num, int left, int right, int st, int fin, long long diff) {
	update_lazy(num, st, fin);
	if (left > fin || right < st) return;
	if (left <= st && right >= fin) {
		Tree[num] += (diff * (fin - st + 1));
		if (st != fin){
			lazy[num * 2] += diff;
			lazy[num * 2 + 1] += diff;
		}
		return;
	}
	int mid = (st + fin) / 2;
	change_Tree(num * 2, left, right, st, mid, diff);
	change_Tree(num * 2 + 1, left, right, mid + 1, fin, diff);
	Tree[num] = Tree[num * 2] + Tree[num * 2 + 1];
}

long long get_sum(int num, int left, int right, int st, int fin) {
	update_lazy(num, st, fin);
	if (left > fin || right < st) return 0;
	if (left <= st && right >= fin) return Tree[num];
	int mid = (st + fin) / 2;
	long long left_sum = get_sum(num * 2, left, right, st, mid);
	long long right_sum = get_sum(num * 2 + 1, left, right, mid + 1, fin);
	return (left_sum + right_sum);
}

void solve() {
	int height = ceil(log2(N));
	Tree.resize((1 << (height + 1)) * 2);
	lazy.resize((1 << (height + 1)) * 2);
	segment_tree(1, 0, N - 1);
	for (int i = 1; i <= M + K; i++) {
		int a, b, c;
		long long d;
		cin >> a;
		if (a == 1) { // add d -> b to c
			scanf("%d %d %lld", &b, &c, &d);
			change_Tree(1, b - 1, c - 1, 0, N - 1, d);
		}
		else { // sum b to c
			scanf("%d %d", &b, &c);
			cout << get_sum(1, b - 1, c - 1, 0, N - 1) << "\n";
		}
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) scanf("%lld", &Index[i]);
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.