Segment Tree - Codeforces

Problem

The problem that a segment tree can solve is the following. We are given an array of values a[0], a[1], ..., a[N - 1]. Assume without loss of generality that N = 2ⁿ; we can generally pad the computations accordingly. Also, consider some associative binary function f. Examples of f include sum, min, max, or gcd (as in the Timus problem). Segment trees allow for each of the following two operations on O(logN) time:

• compute f(a[i], a[i + 1], ..., a[j]) for i ≤ j; and
  
• update a[x] = v.

Read full article from Segment Tree - Codeforces