Be insensitive, and keep a lifelong growth mindset.

0%

## 1. Segment Tree Definition

In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. Segment tree could be implemented using either an array or a tree. For an array implementation, if the element at index i is not a leaf, its left and right child are stored at index 2i and 2i+1 respectively.

## 2. Segment Tree Problems

### 2.1. Range Sum Query - Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

This is a classic segment tree problem, and we can break it down to the three following steps:

1. Build the segment tree;
2. Update the segment tree when an element is modified;
3. Calculate the range sum query using the segment tree.

#### 2.1.1. Build segment tree

Here, we use array implementation as example:

Complexity Analysis:
The total amount of nodes is:
n + n/2 + n/4 + n/8 + … + 1 ~= 2n

• Time complexity: O(n)
• Space complexity: O(n)

#### 2.1.2. Update segment tree

When updating the array at i, we need to rebuild the segment tree as well. Here, we use a bottom-up approach.

Complexity Analysis

• Time Complexity: O(log n);
• Space complexity: O(1);

#### 2.1.3. Range Sum Query

• Loop till l <= r
• Check if l is right child of its parent P
• l is right child of P. Then P contains sum of range of l and another child which is outside the range and we dont’t need parent P sum. Add l to sum without its parent and set l to the next node on the same level.
• l is not right child of P. Then parent P contains sum of range which lies in [l, r]. Add P to sum and set l to point to the parent of P
• Check if r is left child of its parent P
• r is left child of P: Then P contains sum of range of r and another child which is out side the range and we don’t need parent P sum. Add r to sum without its parent and set r to the previous node on the same level
• r is not left child of P. Then parent P contains sum of range which lies in [l, r]. Add P to sum and set r to point to the parent of P.

Drawing a graph by yourself will help a lot!

Here’s the code.

Complexity Analysis

• Time complexity: O(log n)
• Space complexity: O(1)

### 2.2. Range Sum Query 2D

TODO

### 2.3. The Skyline Problem

Suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B). For instance, the dimensions of all buildings in Figure A are recorded as:
[[2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8]]

The skyline in Figure B should be represented as:
[[2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0]].

#### 2.3.1. Solution without segment tree

The idea is very straightforward and can be divided into the following 4 steps:

1. Create a list of all the nodes that sorted by the position in x axis;
2. Create a height array with the size of all nodes, and map the position in x axis to the array index;
3. Iterate all the buildings and update the height values in array.
4. Iterate the array and generate the final result.

Here’s the complet code.

#### 2.3.2 Solution with segment tree

Do we have better solution? Yes! Now we are going to use the segment tree approach to solve it.

In this case, since more than one value needs to be saved for each node: height, start and end, so it’s better to use the tree node implementation instead of the array implementation.

Comparing wiht the solution without segment tree, when we update the nodes’ height values, if we reach a tree node with an equal or higher height values, we can just ignore this building and continue to the next one. This makes the solution more efficient.

### 2.4. Count of Smaller Numbers After Self

TODO