The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

# 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.

# 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 of queries is large.
A segment tree lets us process such queries efficiently in logarithmic order of time.

# How do we make a segment tree?
The process of implementing a segment tree is pretty easy. Let the data be in **arr[]**
1. The **root** of our tree will represent the entire interval of data that we are interested in, i.e, **arr[0...n-1]**.
2. Each **leaf** of the tree will represent a range consisting of just a single element. Thus the leaves
represent **arr[0]**, **arr[1]**, … , **arr[n-1]**.
3. The **internal nodes** will represent the merged result of their **child nodes**.
4. Each of the **children nodes** could represent approximately half of the range represented by their
**parent**.

While implementing a *segment tree*, we generally need to define three types of methods: `BUILD()`, `QUERY()`, `UPDATE()`. Let us discuss each method once.

## `BUILD()`
We visit each leaf of the *Segment Tree*. That makes **n** leaves. Also, there will be **n-1** internal nodes.
So we process about **2 * n** nodes. This makes the Build process run in $O(n)$ linear complexity.
## `UPDATE()`
The update process discards half of the range for every level of Recursion to reach the appropriate leaf in the tree. This is similar to binary search and takes logarithmic time. After the leaf is updated, its direct ancestors at each level of the tree are updated. This takes time linear to the height of the tree.
So the complexity will be $O(log(n))$.
## `QUERY()`
The query process traverses depth-first through the tree looking for the node(s) that match exactly with the queried range. At best, we query for the entire range and get our result from the root of the segment tree itself. At worst, we query for an interval or range of size **1** (which corresponds to a single element), and we end up traversing through the height of the tree. This takes time linear to
the height of the tree. So the complexity will be $O(log(n))$.


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

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Introduction to Segment Trees

What is a segment tree?