Segment tree

A segment tree splits the array in halves, again and again, down to single elements. Every node keeps the sum of its range, so a range sum adds up just a few nodes and an update fixes just one path. Watch Akshay's SegmentTree build the tree with buildSegmentTree, answer sumRange with query, and change a value with update, all recursive.

In the segment tree each box is a SegmentNode: its sum inside, its range under it (a dash while its children are still being built). Each leaf sits right above its index in nums, and the box over nums is the current node's range.