Задача №938. Дерево Фенвика
Дерево Фенвика \(-\) это структура данных, эффективно поддерживающая запросы о сумме префикса числового массива. Для числа \(t\) обозначим \(h(t)\) максимальное значение \(k\), такое что \(t\) делится на \(2^k\). Например, \(h(24) = 3\), \(h(5) = 0\). Обозначим \(l(t) = 2^{h(t)}\), например, \(l(24) = 8\), \(l(5) = 1\).
Рассмотрим массив \(a[1]\), \(a[2]\), \(\ldots\) , \(a[n]\) целых чисел. Дерево Фенвика для этого массива~--- это массив \(b[1]\), \(b[2]\), \(\ldots\), \(b[n]\), такой что \(\) \sum\limits_{j=i-l(i)+1}^{i}a[j] \(\) Таким образом: \(b[1] = a[l]\), \(b[2] = a[l]+a[2]\), \(b[3] = a[3]\), \(b[4] = a[l]+a[2]+a[3]+a[4]\), \(b[5] = a[5]\), \(b[6] = a[5]+a[6]\), Например, дерево Фенвика для массива \(a = (3, -1, 4, 1, -5, 9)\) есть массив \(b = (3, 2, 4, 7, -5, 4)\).
Назовем массив само-фенвиковским, если он совпадает со своим деровом Фенвика. Напрмер, массив \(a = (0, -1,1,1,0,9)\) таковым является.
Вам дан массив \(а\). Вам разрешается заменять в нем некоторые элементы, не меняя их порядка, чтобы сделать из исходного массива само-фенвиковский. Количество изменений при этом должно быть минимально возможным.
В первой строке входных данных содержится количество чисел в массиве \(n\) (\(1 \leq n \leq 100 000\)). Во второй строке находятся сами \(n\) целых чисел. Все числа по модулю не превосходят \(10^9\).
Выведите \(n\) чисел \(-\) элементы видоизмененного массива. Если решений несколько \(-\) выведите любое из них.
6 3 -1 4 1 -5 9
0 -1 1 1 0 9