Medium
Fenwick tree index traversal via i & -i
For n = 8, calling update(bit, 8, 5, delta) with the code below touches which 1-indexed array positions, and why does the loop terminate in O(log n) steps?
main.cpp
void update(vector<long long>& bit, int n, int i, long long delta) {
for (; i <= n; i += i & (-i))
bit[i] += delta;
}
long long prefixSum(vector<long long>& bit, int i) {
long long sum = 0;
for (; i > 0; i -= i & (-i))
sum += bit[i];
return sum;
}11 of 46 in Data Structures & Algorithms