아무 말

IDEA Ternary search는 아래로 볼록인 함수에서 최솟값, 위로 볼록인 함수에서 최대값을 찾을 때 이용할 수 있다. 어떤 함수 \( f(\boldsymbol{\mathrm{x}}) \)가 있다고 하자. 이 함수는 \(\boldsymbol{\mathrm{x}}_i \) for all \(i\)에 대해서 아래로 볼록이다. 즉, fixed \(\boldsymbol{\mathrm{x}}_j\) for all \(j \neq i\) 이면, \(f(\boldsymbol{\mathrm{x}})\)는 아래로 볼록이다. 이때, 각 \(\boldsymbol{\mathrm{x}}_i\)에 대해서 ternary search를 이용해 optimization을 해주면, 함수는 조금씩 최적화 될 것이라는 생각을 할 수 ..

INTRODUCTION Segment tree를 이용해서 수열에서의 구간 합을 구하는 방법은 매우 잘 알려져 있다. 본문에서는 수열의 값이 0 또는 1밖에 없을때 이를 더 빠르게 처리하는 방법에 대해서 다루고자 한다. IDEA 컴퓨터에서 bit의 수를 세는 것은 \(O(1)\)에 수행할 수 있다. 또한, 이 bit를 셀 때 세고싶은 구간만 나눌 수 있다. 간단히 원하는 구간만 1로 채워져 있는 bitset과 bitwise AND 연산을 이용하면 된다. 그렇다면 이것으로 구간 쿼리를 처리하는 방법에 대해 감이 어느정도 왔을 것이다. Segmet tree의 맨 아래쪽 리프를 모두 bitset으로 만든다. 그리고 나머지는 원래대로 처리하면서 리프의 bitset에서 값이 1인 bit의 수를 세서 위쪽 리프로 올..