[일반] 이런 자료구조도 있습니가?? (세그먼트 트리?)

[익명(211.34)]

query(a, b): [a,b] 구간의 최솟값

update(a, b, v): [a,b] 구간의 값을 v로 대치

암만 찾아봐도 v를 더하는 update 밖에 없어요..

[0xrgb(0xrgb)]

lazy propagation 한방이면 해결됨

[0xrgb(0xrgb)]

BBST 하나 만들어서 split 가지고도 가능

[익명(211.34)]

감사합니다. 혹시 펜윅으로도 구현되나요? 그냥 궁금해서요

[0xrgb(0xrgb)]

아니요

[하루룽(ailedear)]

굳이 펜윅으로 저 update 만들려면 O(NlgN)인가?

[0xrgb(0xrgb)]

최소값만 구하게 해도 힘들껄

[하루룽(ailedear)]

ㅇㅎ 최솟값이구나