Trees

Serving sums

You are building a machine whose initial state is a list of $n \geq 1$ zeros. The machine responds to two types of instructions. The first, called a write, asks to increment the number at a given position by a fixed amount. The second, called a read, requests the contiguous sum of all numbers that fall between two specified positions. How would you build the machine if you expect much more writes than reads? What if you expect significantly more reads than writes? What if the number of reads is approximately equal to the number of writes?

Sorting with trees

Can you use binary search trees to sort data?