Segment tree

The segment tree is a highly versatile data structure, based upon the divide-and-conquer paradigm, which can be thought of as a tree of intervals of an underlying array, constructed so that queries on ranges of the array as well as modifications to the array's elements may be efficiently performed.

The problem

Before introducing the structure of the segment tree, we will consider the motivation for its existence. Suppose that you are initially given an array of numbers (natural, integral, real, it doesn't matter) and a series of operations to be performed one after another. Each operation will ask you either to find the sum of all elements within a specified range of indices or to modify one of the array's elements to a new, specified value. For example, suppose the initial array is [9,2,6,3,1,5,0,7] and you are asked to find the sum of the 3rd through 6th elements, inclusive. Then you would answer 15 (which is 6+3+1+5). Next, you are asked to change the 5th element to 8. Then, you are asked for the sum of the 4th through 8th elements. You answer 23 (which is 3+8+5+0+7).