Segment Tree

Introduction

Segment Trees are intuitively named as they store information about array intervals as a tree structure. This allows for quick operations like finding the minimum element in a range $a[l\dots.r]$ or finding the sum of consecutive array elements. The simplest form of a segment tree supports two operations, both of which must be completed in O($\log{n}$):

1. Find the sum of elements between indices $l$ and $r$
2. Change the values of the elements in an array

The actual structure of the tree is simple. As the name suggests, we store segments of the array to form a binary tree. So the top-level node contains a[0...n] accompanied by some metadata relating to the segmentLike a sum. Here is an example with an array of n == 5

You'll notice that each leaf node is just one element in the original array (a[3...3] == a[3]). These leaves start as the building blocks for the rest of the tree. Given that we have the metadata, like sum, for each element, the tree utilizes a merge operation that will build the tree from the ground up.

Sum Queries

A very common application or use-case of a segment tree are sum queries. Essentially, we want to find the sum between $l$ and $r$ in the fastest way possible. It should be clear that the segment tree structure allows us to do this in O($\log{n}$) time. There are three general cases when presented with a sum query. The first is that you already are at the vertex of the desired range. The second is that either the right or left vertex contains the desired rangeAnd then continue the process described here. The third case is the most nuanced. Suppose the query range intersects both children, meaning we have an $l$ outside of the current vertex and an $r$ outside the current vertex. When I first tried understanding this it was pretty convoluted, but here is an example to make you understand it better. Suppose you are at a root node covering [0...7], and a query of [2...6] comes in. The midpoint here is 7 // 2 = 3, so recurse on the left subtree to find the sum of range [2..3] and the right subtree to find [4..7].

Update Queries