이 글에서는 구간 트리(segment tree), 펜윅 트리(fenwick tree), 느리게 갱신되는 구간 트리(segment tree with lazy propagation)들이 성립하는 조건을 알아볼 것이다. 다만, 이 글에는 한계가 존재한다. 구간 트리를 하나의 Black-Box(기능은 알지만 작동 원리를 이해할 수 없는 복잡한 기계 장치나 시스템, 물체)로 바라보기 때문에 직사각형들의 합집합의 넓이를 구하는 문제와 같이 구간 트리의 구조를 변형시키는 문제에는 이 글의 내용이 적용이 되지 않을 수 있다. 기본 질의응답의 대상인 배열은 $[a_1,a_2,\ldots,a_n]$이다. 배열 속 원소들을 포함하는 집합 $S$, 원소들 간의 이항 연산 $*$, 갱신 함수의 집합 $F$가 있다. 이때, 당연..

문제 링크 문제에 풀 때 사용할 수 있는 자료구조 테크닉(문제 특성에 비해 약간 오버킬)을 배울 수 있어 좋았다. 또한, 풀이만 6개를 확인했는데... 진짜 이런 고난이도에 조건이 적은 문제는 여러 방법으로 접근할 수 있구나... 싶었다. Subtask: $N ≤ 3\ 000, Q ≤ 3\ 000$ (2점) 더보기 Naive하게 짜면 된다. 2점이라 짜다고 생각했는데 풀고 나니 걸맞는 점수다 ㅋㅋ 코드 Subtask: 점수 $ ≤ 10^5, Z_j =0$ (20점) 더보기 난이도가 확 뛴다. 우선, 각 점수 쌍들을 좌표로서 해석하면 시각화가 되므로 풀이에 접근하기 좋다. 시각화 이후에 간단한 관찰들을 바탕으로 떠오르는 자료구조들이 있을 것이다. 그렇게 다음의 3가지 풀이가 있다: Merge sort tr..