Challenge: Implement Your Own

Before moving on, implement a BIT from scratch without looking at notes:

$1.$ Implement update(i, delta) and query(i)

$2.$ Build a BIT from an array

$3.$ Test with range sum queries

$4.$ Verify against brute force

Once you can write it in under 2 minutes, you have internalized the pattern.

// Template to fill in:
class BIT:
    function init(n):
        // Your code

    function update(i, delta):
        // Your code

    function query(i):
        // Your code

    function rangeQuery(l, r):
        // Your code

The best way to learn data structures is to implement them from memory.