Introduction to Binary Indexed Tree Pattern

You are given an array, and two kinds of request mixed together. Report the sum of everything up to a position, and add a value at one position.

[3, 1, 4, 1, 5, 9, 2, 6]
sum up to position 5?   3 + 1 + 4 + 1 + 5 = 14
add 4 at position 2
sum up to position 5?   18

Two simple structures each fail on one side. A prefix array answers the query in O(1), but one change rewrites every entry after it, which is O(N). The plain array updates in O(1), but the query then adds up O(N) values.

Neither is a good trade, because the requests are mixed