Lazy Propagation
Lazy Propagation 배열의 구간 쿼리, 구간 합을 빈번하게 수행할 때 비교적 적은 횟수로 쿼리를 수행하는 방법 Segment Tree, Fenwick Tree 활용의 연장선에 있다. 배열 X에서 구간 쿼리를 수행하고 구간 합을 구할 때 한 개의 트리만 사용할 경우 구간의 길이만큼 쿼리를 수행해야 한다. 이때 추가적인 트리를 사용하면 쿼리를 적은 횟수 수행하고 두 트리를 모두 사용해 구간 합을 구할 수 있다. 0으로 초기화된 배열 X에서 다음 구간 쿼리를 수행한다고 하자. [4,9]에서 +6 [3,6]에서 -2 두 세그먼트 트리/펜윅 트리 a, b를 아래와 같이 이용할 수 있게 update하자. 구간 [1,4]의 합을 구하는 경우, [1,4] 내에서 6은 X[4]에, -2는 각각 X[3], X[..
2021. 8. 13.
단축키
내 블로그
| 내 블로그 - 관리자 홈 전환 |
Q
Q
|
| 새 글 쓰기 |
W
W
|
블로그 게시글
| 글 수정 (권한 있는 경우) |
E
E
|
| 댓글 영역으로 이동 |
C
C
|
모든 영역
| 이 페이지의 URL 복사 |
S
S
|
| 맨 위로 이동 |
T
T
|
| 티스토리 홈 이동 |
H
H
|
| 단축키 안내 |
Shift + /
⇧ + /
|
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.
