넘치게 채우기

https://www.acmicpc.net/problem/10999BOJ - 구간 합 구하기 2문제 유형: 세그먼트 트리 (with lazy propagation)문제 난이도: Platinum IV시간 제한: 2초메모리 제한: 256MB 문제어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째부터 4번째 수에 6을 더하면 1, 2, 9, 10, 5가 되고, 여기서 2번째부터 5번째까지 합을 구하라고 한다면 26을 출력하면 되는 것이다. 그리고 그 상태에서 1번째부터 3번째 수에 2를 빼고 2번째부터 5번째까지 합을 구하라고 한다면 22가 될 것이다. 입력첫째 줄에 수의 개수 N(1 ≤ N ≤..

세그먼트 트리References:https://youtu.be/-dUiRtJ8ot0?si=SRjeBHChrzUaN-id  세그먼트 트리란, 1차원 배열에서의 구간 연산에 대해 빠르게 구하는 자료구조이다.구간 [l, r]에 대해서 기존의 naive하게 업데이트 및 연산하는 것은 O(N)의 시간이 걸리지만,세그먼트 트리를 이용하면 O(log N)의 시간이 걸린다. 세그먼트 트리는 트리이지만, 배열 기반의 이진트리로 간단하게 표현될 수 있다.이진트리의 특성상, 0-based의 기준, 인덱스 i 노드의 왼쪽 자식은 i*2+1, 오른쪽 자식은 i*2+2에 위치한다.1-based의 기준, i노드의 왼쪽 자식은 i*2, 오른쪽 자식은 i*2+1이다. 세그먼트 트리에서,루트 노드는 모든 구간에 대한 연산 결과를 저장한..