최근에 세그먼트 트리라는 새로운 데이터 구조가 나왔고 2 차원으로 확장 될 수 있다고 읽었지만 구현 세부 정보를 읽을 수있는 좋은 소스를 찾을 수 없었습니다. 및 기타 물건. 그래픽 분야가 아닌 프로그래밍 콘테스트에서 사용하는 관점에서 배우고 싶습니다. 사용하여 해결할 수있는 몇 가지 문제도 유용 할 것입니다. 누군가가 좋은 소식을 들려주기를 바랍니다. 감사합니다.쿼드 트리 - 멀티 레벨 세그먼트 트리
자세한 소식통을 찾으려면 확실하지 않습니다. 나는 k 차원의 세그먼트 나무가 어떻게 작동하는지 이해하는 것이 사람들에게 맡겨진다고 생각합니다. 당신의 입장에서 나는 그것으로 할 수있는 문제를 해결하려고 노력할 것입니다. 간단한 예제 (그리고 나는이 쿼리가 일부 전처리를 통해 O (1)에서 수행 될 수 있음을 알고있다) : 직사각형 범위 합계. 즉, 숫자로 채워진 행렬이 주어지면 부분 행렬 합계를 묻는 질의에 응답합니다. 여기에서는 하나의 semgent 트리를 사용하여 높이를 분할 한 다음 각 노드에 너비 기반 합계에 대한 추가 세그먼트 트리를 만들 수 있습니다. 그렇게 할 수 있다면 2 차원에 대해 알아야 할 모든 것을 알 것입니다. 세그먼트 나무. 다음 과제는 단일 요소를 업데이트하는 것입니다. 일부 아트를 사용하여 변경 사항을 적절하게 전파해야하므로 (세그먼트 트리 내부에서 일부 유형의 캐싱) :)
코드 샘플을 사용하여 1D 세그먼트 트리와 2D 일반화에 대한 좋은 기사가 있습니다. 당신은 아마 단지 코드 샘플을 생각해야 할 것입니다 그래서하지만 특히 프로그래밍 대회에 매우 어렵고 시간이 많이 걸릴 수 판명 수 있습니다, 여러 차원에 세그먼트 트리를 확장
) =, 러시아어입니다.
여러 차원이 필요한 경우 먼저 이진 인덱스 트리에 대해 알아야하며 여러 차원으로 확장 해보십시오.
이진 인덱싱 된 트리는 경우에 따라 세그먼트 트리보다 성능이 뛰어나지 만 다른 세그먼트에서는 단순히 부적합한 데이터 구조입니다.
세그먼트 트리를 사용할 때 여러 차원의 확장이 쉽습니다.
여기서 an article about them을 찾을 수 있습니다.
여기서 a problem that can help you test your implementation을 찾을 수 있습니다.