To add to position , update all positions that include in their range: def update(i, delta): while i <= n: tree[i] += delta i += lowbit(i) Example: update position : - Update tree[3] (covers element 3) - - Update tree[4] (covers elements 1-4, includes 3) - - Update tree[8] (covers elements 1-8, includes 3) - Continue until exceeding Each position's responsibility range either includes entirely or not at all.
You update exactly those that include it. Time: iterations.