D031

Counting 1’s

이 문제는 스트림이 0이나 1의 비트로 구성되었을 때
최근 k ($k \le N$) 비트에서 1이 몇개가 나왔는지 찾는 문제입니다.

단순하게 N 크기의 비트를 저장해서 1의 수를 카운트해서 출력하는 방식을 생각해 볼 수 있습니다.
그러나 이 방식은 쿼리를 수행하는데 O(k) 시간이 소요되고
N 이 큰 경우 저장조차 못하기 때문에 적합한 방식이 아닙니다.

블록을 기하급수적으로 늘리면서 스트림을 요약합니다.

블록이 기하 급수적으로 늘어남에 따라 스트림 블록을 요약합니다.

길이가 증가하면 1, 2, 4, 8, 16 등이됩니다.