펜윅 트리

시간 제한3초메모리 제한256 MB

요약

배열이 자기 자신의 펜윅 트리(BIT)와 같아지도록 값을 바꿔야 하는 원소의 최소 개수를 구하는 문제입니다.

난이도: 보통10점 중 6점
유형: 수학, 트리, 구현
정답자: 아직 제출이 없습니다

문제

펜윅 트리(Fenwick tree)는 구간 합(prefix sum) 질의를 효율적으로 지원하는 자료구조이다.

양의 정수 $t$ 에 대해, $t$ 가 $2^k$ 로 나누어떨어지는 가장 큰 $k$ 를 $h(t)$ 라 하자. 예를 들어 $h(24) = 3$ , $h(5) = 0$ 이다. 그리고 $l(t) = 2^{h(t)}$ 로 정의하면 $l(24) = 8$ , $l(5) = 1$ 이 된다. 즉, $l(t)$ 는 $t$ 에서 가장 낮은 자리에 켜져 있는 비트(lowest set bit)의 값과 같다.

정수 배열 $a[1], a[2], \dots, a[n]$ 이 주어졌을 때, 이 배열의 펜윅 트리는 다음과 같이 정의되는 배열 $b[1], b[2], \dots, b[n]$ 이다.

$b[i] = \sum_{j=i-l(i)+1}^{i} a[j].$

예를 들어

b[1] &= a[1], \\ b[2] &= a[1] + a[2], \\ b[3] &= a[3], \\ b[4] &= a[1] + a[2] + a[3] + a[4], \\ b[5] &= a[5], \\ b[6] &= a[5] + a[6], \end{aligned}$$ 와 같이 계속된다. 구체적인 예로, $a = (3, -1, 4, 1, -5, 9)$의 펜윅 트리는 $b = (3, 2, 4, 7, -5, 4)$이다. 어떤 배열이 자기 자신의 펜윅 트리와 같을 때, 그 배열을 **자기 펜윅(self-fenwick)** 배열이라고 부른다. 위 배열은 자기 펜윅 배열이 아니지만, $a = (0, -1, 1, 1, 0, 9)$는 자기 펜윅 배열이다. 배열 $a$가 주어진다. 원소들의 위치와 순서는 그대로 둔 채 일부 원소의 값을 바꾸어, 결과 배열 $a'$가 자기 펜윅 배열이 되도록 만들 수 있다. 이때 **바꿔야 하는 원소의 최소 개수**를 구하여라.

입력

첫째 줄에 배열의 원소 개수 $n$ 이 주어진다 ( $1 \le n \le 100\,000$ ).

둘째 줄에 배열의 원소인 $n$ 개의 정수가 주어진다. 각 원소의 절댓값은 $10^9$ 을 넘지 않는다.

출력

배열이 자기 펜윅 배열이 되도록 하기 위해 바꿔야 하는 원소의 최소 개수를 정수 하나로 출력한다.

예제5

예제 1
입력
```
6
3 -1 4 1 -5 9
```
예상 출력
```
3
```
예제 2
입력
```
6
0 -1 1 1 0 9
```
예상 출력
```
0
```
예제 3
입력
```
1
5
```
예상 출력
```
0
```
예제 4
입력
```
2
3 5
```
예상 출력
```
1
```
예제 5
입력
```
8
1 2 3 4 5 6 7 8
```
예상 출력
```
4
```