Segment Tree with Bitset

INTRODUCTION

Segment tree를 이용해서 수열에서의 구간 합을 구하는 방법은 매우 잘 알려져 있다. 본문에서는 수열의 값이 0 또는 1밖에 없을때 이를 더 빠르게 처리하는 방법에 대해서 다루고자 한다.

 

IDEA

컴퓨터에서 bit의 수를 세는 것은 \(O(1)\)에 수행할 수 있다. 또한, 이 bit를 셀 때 세고싶은 구간만 나눌 수 있다. 간단히 원하는 구간만 1로 채워져 있는 bitset과 bitwise AND 연산을 이용하면 된다. 그렇다면 이것으로 구간 쿼리를 처리하는 방법에 대해 감이 어느정도 왔을 것이다. Segmet tree의 맨 아래쪽 리프를 모두 bitset으로 만든다. 그리고 나머지는 원래대로 처리하면서 리프의 bitset에서 값이 1인 bit의 수를 세서 위쪽 리프로 올려주는 것 만으로 구간 합 쿼리를 처리할 수 있다. 이로써 시간복잡도와 공간복잡도의 상수를 최적할 수 있다.

 

Lazy propagation 또한, 이 아이디어를 이용한 segment tree에 적용할 수 있다. 구간 update query를 처리할 때의 방법에서 leaf update만 신경써주면 된다.

 

CODE

BOJ 1395번을 이  최적화를 통해 해결한 코드이다.

https://github.com/P4rkingZ0eN/Well_Known/blob/main/SegtreeWithBitset.cpp

 

이 최적화를 구현한 Segtree이다. Bit의 상태를 바꾸는 것만 구현해 두었지만, 특정 구간의 bits의 상태를 모두 1이나 0으로 바꾸는 query도 충분히 본문의 아이디어를 이용할 수 있다.

https://github.com/Sora-Sugiyama/Libs/blob/main/Data-Structure/bitSegtree.h