SEGMENT TREES

  1. update i value: Update element of array A at index i with value.
  2. query l r: Print the sum of the array A from index l to index r.
  1. update i value: Update the element in the array A at index i with value.
  2. query l r: Print the min of the array A from index l to index r.
  1. UPDATE i value: Update the element in the array A at index i with value.
  2. QUERY l r: Print the gcd of the array A from index l to index r.

When should I use a segment tree?

  1. The function f must be associative:
    i.e. f(a,b,c) = f(a,f(b,c)) = f( f(a,b),c). The functions in the above problems are addition, min, and gcd which are associative.
    For addition let f(a,b) denote a+b.
    f(a,b,c) = a+b+c = a+(b+c) = f(a,f(b,c)) = (a+b)+c = f(f(a,b),c).
    We can prove similar results for min(a,b) and gcd(a,b) as well.
    We can extend this result to a range [l,r] as follows:
    Let g(l,r) denote the application of the binary function f(a,b) on all the elements array A in the range l to r.
    thus, g(l,r) = f(A[l],A[l+1],A[l+2]…..A[r])
    also as f(A[l],A[l+1],A[l+2]…..A[r]) = f(A[l..k],f(A[k+1..r]) for some k in the range [l,r].
    this makes g(l,r) = g(g(l,k),g(k+1,r)).
  2. The answer of an interval [l,r] can be derived from the answer of a smaller interval by adding some interval to it or by the answer of a bigger interval by subtracting some interval from it.
    For addition let f(a,b) denote a+b.
    Let g(l,r) denote the application of the binary function f(a,b) on all the elements array A in the range l to r.
    thus, g(l,r) = f(A[l],A[l+1],A[l+2]…..A[r])
    g(l,r) = g(0,n-1)-g(0,l-1)-g(r+1,n-1) (0≤l<r≤n-1)
    g(l,r) = g(k,p) + g(l,k-1) + g(p+1,r) (l≤k<p≤r)
    We can prove similar results for other function as well.
    If your function follows the above conditions then a segment tree can be used to solve the problem.

Segment tree : Structure

The original Array A consists of four elements
Segment tree that stores the results of various intervals of the array A
Pictorial representation of array A
The range sum segment tree for array A with intervals and results.
Pictorial representation of array A
The range min segment tree for array A with intervals and results.
Pictorial representation of array A
The range gcd segment tree for array A with intervals and results.

Segment tree : Array representation

An array with 4 elements has the indexes 0,1,2,3.
The corresponding segment tree for the array in the image above
Representing the segment array in form of an array

Segment tree : The build function

Segment tree : The query function

If end<query_start then there is no overlap between the query interval and node interval
If start>query_end then there is no overlap between the query interval and node interval
if query_start≤start and end≤query_end we get complete overlap
(query_start≤start≤query_end and query_end≤end)
(start≤query_start and query_start≤end≤query_end)

Segment tree : The Update function

Pictorial representation of array A
Range minimum segment tree for given array A
Updated array A
The updated segment tree with new min value.

Segment tree : Complexity Analysis

Putting it all together

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Saurabh Ojha

Saurabh Ojha

I want to be a better sports programmer. Passionate about algorithms and optimisations.