SegmentTree 디자인 개선

[byeongkeunahn]

• Lazy ops 지원을 추가해야 합니다. 이를 위해서는 먼저 Lazy SegmentTree의 API 디자인을 정해야 합니다.
• 기존 non-lazy SegmentTree의 API 디자인도 개선할 수 있습니다.
• SegmentTree, SplayTree 등의 사용례를 모두 포괄할 수 있어 범용성이 높은 B+ tree 기반의 마스터 구현체를 추가하고, SegmentTree는 이 구현체의 thin wrapper로 두는 방법도 고려하고 있습니다.

[kiwiyou]

일반적인 Lazy Segment Tree의 용례에서 필요한 기능은 다음과 같습니다.

• 원소의 타입 T와 업데이트의 타입 U
• T 위의 이항연산 *
• 업데이트 함수 f: U×T→T
• 업데이트의 합성 ∘
• ∘에 대한 항등원

이외에 더 필요한 게 있을까요?

[byeongkeunahn]

아뇨 충분한 것 같습니다.

그리고 참고를 위해 B+ tree의 사용례를 하나 기록합니다. 좌표압축이나 동적세그트리가 필요한 문제에서 B+ tree를 사용하고 key를 좌표, value를 monoid 원소로 고려하면 훨씬 간결하게 구현할 수 있을 것 같습니다.

[kiwiyou]

B+ Tree가 완전히 Splay Tree를 대체할 수 있는지, 같은 인터페이스를 제공할 수 있는지는 잘 모릅니다. 하지만 Segment Tree라면 벤치마킹 후에 기본 구현으로 도입해도 좋을 것 같습니다.

[byeongkeunahn]

벤치마크는 필요하겠네요. 결과차이가 크면 분리할게요.

Splay Tree의 경우 interval flip 기능이 특징적인데 B+ tree에서도 tree split, concat 연산을 통해 구현이 가능하다고 알고 있습니다. 조금 더 검토해보겠습니다.