[알고리즘 문제 모음] 구간 합(누적 합, 세그먼트 트리, 펜윅 트리)

 

 

 

 

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.*

★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다.

+가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다.

 

기본 누적합 문제 

백준 - 개똥벌래(3020) - Gold 5

 

 

세그먼트 트리 문제

백준 - 구간 합 구하기(11658) + 세그먼트 트리 - Gold 1

백준 - 최솟값과 최댓값(2357) + 세그먼트 트리 - Gold 1

백준 - 구간 곱 구하기(11505) + 세그먼트 트리 - Gold 1

백준 - 공장(7578)★ + 세그먼트 트리, Inversion Counting  - Platium 5

알고스팟 - 족보 탐험(FAMILYTREE)★+ LCA + 세그먼트 트리 - 상

 

 

느리게 갱신되는 세그먼트 트리(Segment Tree and Lazy Propagation)

백준 -구간 합 구하기 2(10999)★+ 느리게 갱신되는 세그먼트 트리-Platium 4

백준 -스위치 (1395)+ 느리게 갱신되는 세그먼트 트리-Platium3

 

 

 

펜윅 트리(Fenwick Tree) 문제

알고스팟 - 삽입 정렬 시간 재기(MEASURETIME) + 펜윅 트리 - 중

백준 - 구간 합 구하기 3(11658)★ + 펜윅 트리 - Platium 5

백준 -수열과 쿼리 21(16975)★+ 펜윅 트리-Platium 4

백준 -LRH 식물(2934) + 펜윅 트리-Platium 4

 

 

 

 

Lazy Propagation Fenwick Tree

[Fenwick Tree Lazy propagation] - 펜윅 트리에 Lazy propagation 적용하기