Competitive Programming - Crack Your Coding Interview, C++/

...

/

Introduction to Segment Trees

Introduction to Segment Trees

Learn how segment trees can be useful in solving coding interview problems.

We'll cover the following...

What is a segment tree?

A segment tree is a full binary tree where each node represents an interval. Generally, a node would store one or more properties of an interval that can be queried later. Look at the illustration below to get a sense of how a segment tree is structured.

%0 node_1 A[0:3] node_2 A[0:1] node_1->node_2 node_3 A[2:3] node_1->node_3 node_1610896502704 A[0] node_2->node_1610896502704 node_1610896504168 A[1] node_2->node_1610896504168 node_1610896491388 A[2] node_3->node_1610896491388 node_1610896483846 A[3] node_3->node_1610896483846
Segment Tree of an Array consisting of 4 Elements

How does the above segment tree look in memory?

Like Heap, the segment tree is also represented as an array. The difference here is that it is not a complete binary tree. Rather, it is a full binary tree (every node has 0 or 2 children) and all levels are filled except possibly the last level. Unlike Heap, the last level may have gaps between nodes. Given below are the values in the segment tree array for the above diagram.

Below is the memory representation of the segment tree for input array {1, 3, 5, 7, 9, 11}

st[] = {36, 9, 27, 4, 5, 16, 11, 1, 3, DUMMY, DUMMY, 7, 9, DUMMY, DUMMY}

Why do we need a segment tree?

Many problems require that results are given based on queries over a range or segment of available data. This can be a tedious and slow process, especially if the number ...