Building a Fenwick Tree

Two approaches to build from an array:

Approach 1: $n$ updates. $O(n \log n)$

tree = [0] * (n + 1)
for i in range(n):
    update(i + 1, arr[i])

Approach 2: Linear build. $O(n)$

tree = [0] + arr[:]  # 1-indexed copy
for i in range(1, n + 1):
    j = i + lowbit(i)
    if j <= n:
        tree[j] += tree[i]

The linear approach propagates each position's value to its parent in the BIT structure.

For most competitive programming, the $O(n \log n)$ approach is fine and simpler to remember.