[일반] god님들 2d 세그먼트 트리가 도대체 뭔가요

[뉴비(220.92)]

그냥 벡터같은데다가 vector >이런식으로 세그먼트 트리를 쭉 여러개 나열해놓은건가요

잘 설명되어있는 글이나 블로그가 찾기 어렵네요..

링크로 남겨주시거나 관련 문제 추천이나, 설명 좀 부탁드릴게요

ㅜㅜㅜㅜㅜㅜ

[뉴비(220.92)]

혹시 persistent segment tree에서 2d 질문을 하는것을 2d세그먼트 트리라고 하나요?

[시아닌(kimjg1119)]

아니요

[ㅅㅅ(1.240)]

x축을 세그먼트 트리처럼 구간으로 나눠서 그 안에 1차원 세그트리를 또 넣는거임. 일반적인 경우 공간 복잡도는 n^2이고 쿼리 시간은 lg^2n pst는 세그먼트 트리에서 업데이트 된 기록을 가지고 있을 수 있음. 즉, 업뎃 전 세그트리와 업뎃 후 세그트리에 전부 쿼리 가능. 이걸 업뎃 할 때마다 lgn씩 공간복잡도 늘어나게 구현 가능함.

[뉴비(220.92)]

정말감사합니다..

[익명(218.54)]

기본적으로 세그에 세그박은거

[뉴비(220.92)]

정말감사합니다..

[시아닌(kimjg1119)]

2018KOI 고등부3 조화로운 행렬이 연습문제에요

[시아닌(kimjg1119)]

구현은 개인적으로 codeforces blog 참조하시는게 좋아보이고 geeksforgeeks는 투디세그에선 걸러요

[뉴비(220.92)]

정말감사합니다..

[뉴비(220.92)]

하나만더여쭤보고싶은덷 혹시 이거 설명 자세하게 되어있는 블로그나 사이트 있나요??

[옥토끼(moonrabbit2)]

pst를 아는데 투디세그를 모른다니 - dc App

[시아닌(kimjg1119)]

모를수도 있지 왜 기를 죽이고 그래

[옥토끼(moonrabbit2)]

[하루룽(ailedear)]

투디세그는 동적으로짜야제맛