Segment tree is a data structure storing intervals. You can update the value of certain position and get the representative value of an interval [begin, end) in O(n lg n) time complexity. The representative value can be the sum, the maximum, or the minimum of the values in each interval.
For detail, see following: