kkw564   2년 전

좀 막 만든 감이 없지않아 있지만,


혹시 펜윅트리로도 최솟값을 구할 수 있나요??(각 구간에서의)

ntopia   2년 전

펜윅트리는 기본적으로 1번부터 x번까지의 대표값을 구하는 트리입니다. 그러니까 min(a[1] ~ a[x])  의 값은 구할 수 있어요.

그런데 이게 임의의 구간에 대해 값을 구하고 싶으면 조금 골치아픕니다.

만약 연산에 역원이 존재하면 역원을 이용해 특정 구간의 대표값을 구할 수 있습니다. 특정 구간의 합을 구하는 예가 대표적이죠. 합 2개를 구한 다음에 차이를 계산하면 되잖아요?

그런데 min 연산은 역원이 없으므로 이런게 불가능합니다.

ntopia   2년 전

헐 이거 띠용한 방법이네요!

펜윅트리 2개를 쓰면 되는군요

좋은 것 배우고 갑니다...

kkw564   2년 전

좋은 정보 가져갑니다~

댓글을 작성하려면 로그인해야 합니다.