sparse table 이건 또 머야

[익명(123.109)]

하... 알고리즘의 세계는

정말 방대하군 세그먼트까지 못가겠네

- dc official App

[마음e(114.203)]

나랑 같이 접자

[익명(123.109)]

그치만 너무 재밋는걸 이해하려고 끙끙댈땐 힘들지만 결국 이해하고 다시 봣을 땐 짜릿해 - dc App

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(123.109)]

일단 값이 업데이트 되는 동적인 상황에선 세그 쓰는것만 이해햇구요 아직 정적 배열에 대해서 구간질의 하는 알고리즘 보고잇어요 prefix sum array랑 sparse table은 이제 이해했어요 재밋네요 이거 nlogn 전처리로 연산을 O(1)에 하는게. 근데 연산의 결합법칙? 교환법칙? 아무튼 먼가 특정한 성질의 연산만 가능한거 같긴하네유 O(n) 전처리하는 피셔알고리즘도 궁금하긴한데 엄두가 안나네요 - dc App

[익명(123.109)]

제가보는 책에는 sparse tree가 길이 2^i인 구간의 최솟값을 모두 저장하네요 펜윅은 sum값만 나오구요 - dc App

[익명(123.109)]

펜윅 마법같네요 정말... 머리아프긴한데 prefix sum array 를 미리 구해야하는 건가요?? - dc App

[익명(123.109)]

아 update로 초기화하면 되는구나 ㅋㅋㅋ - dc App

[kumakuma(rgq1379)]

그거 하면 LCA 뚫을 수 있음 ㅋㅋ - dc App

[익명(123.109)]

그게머에요 - dc App

[마음e(114.203)]

https://m.dcinside.com/board/programming/1967191

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[마e음(222.121)]

쉽네~~