[일반] 코린이 세그가 뭔지 공부하는 중인데

[익명(49.165)]

마법같은 도구로 불려서 찾아보는 중인데 구현은 원래 이렇게 코드 긴 거 맞지?

(트리 만들기, 업데이트, 원하는 행동) 이렇게 3개는 최소 구현하고 가는 것 같은데

[익명(118.235)]

바텀업구현은 짧음

[익명(49.165)]

오 두 종류네 보통 어떤 거 많이 씀? 뭔가 느낌은 바텀업이 업데이트할 때 더 좋을 것 같은데 상관없나

[익명(1.239)]

구현 길어봐야 함수당 다섯줄에 많아야 init update get 필요한거 아님?

[익명(1.239)]

사실 init도 필요없음 저거

[익명(49.165)]

코린이 기준 그 정도면 긴 거였음 update get은 필요하다는 거네 ㄳ

[익명(1.239)]

ㅇㅎㅋㅋㅋ 파이팅

[익명(49.165)]

근데 이닛은 왜 필요 없는 건지 간단하게라도 몇 문장 가능?

[익명(1.239)]

init해도 nlogn n개를 update해도 nlogn

[익명(49.165)]

ㅇㅎ 그러면 구간 합 구하기 이런 거면 업데이트만 만들고 입력 받는 동시에 업데이트 n번 돌리나보네 ㄳ

[익명(211.36)]

init 하면 O(N+QlgN) 안하면 O((N+Q)lgN)이라 하는게 더 빠름

[익명(118.235)]

으 init이 필요없다니 설마 priority queue에도 하나씩 넣고 사는 거 아니지?

[익명(192.166)]

구현 많다길래 굳이 안해도 된댔더니 ㅇㅈㄹ ㅋㅋ

[익명(223.33)]

필요없는 거 맞는데 으 이지랄... 피갤하면서 시간복잡도 개념도 없네

[노는게제일좋아(aig0016)]

근데 init 함수도 어차피 O(NlogN) 아님? 세그를 O(n)에 초기화가 가능함?

[익명(1.239)]

윗놈이 쓴것처럼 차이가 있는건 맞는데 이걸로 tle가 갈리는 수준은 아님