Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

SegmentTree 디자인 개선 #99

Open
byeongkeunahn opened this issue Jun 6, 2024 · 4 comments
Open

SegmentTree 디자인 개선 #99

byeongkeunahn opened this issue Jun 6, 2024 · 4 comments

Comments

@byeongkeunahn
Copy link
Collaborator

byeongkeunahn commented Jun 6, 2024

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

kiwiyou commented Jun 6, 2024

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

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

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

@byeongkeunahn
Copy link
Collaborator Author

아뇨 충분한 것 같습니다.

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

@kiwiyou
Copy link
Collaborator

kiwiyou commented Jun 6, 2024

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

@byeongkeunahn
Copy link
Collaborator Author

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

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants