# Segment Trees

Segment trees are a unique application of trees that help to solve problems that involve many range queries over an array

Whenever you see problems that involve multiple range queries like finding the maximum across ranges, explore using segment trees

The fundamental idea of segment trees is that each leaf corresponds to an element in the array (by index) and each subsequent parent represents a range of that array, `i..j`

. As a result, while segment trees can be represented as an actual tree, it can also just be represented directly using an array.

## Implementation

For this implementation of segment trees, updates are relatively expensive because they have to traverse the entire tree to ensure that all nodes are updated accordingly. To optimize updates, you can look into lazy propagation on segment trees

### Building

Build from bottom up using merge sort like algorithms

### Updating

### Querying

When querying for a range, we're simply looking for the ranges (represented by our nodes) that fully encompass our search range

Last updated