In this topic i will explain a very interesting data structure that can be used to solve a specific set of problems. I will start by explaining its definition and the proceeding with an example problem to solve with it.

**Table of contents:**- What is segment trees?
- Order of growth of segment trees operations
- Show me your code
- Lazy propagation
- Sample problems to try
- References

**What is segment trees?**

Segment Trees is a Tree data structure for storing intervals, or segments, It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. It only uses O(N lg(N)) storage.

A segment trees has only three operations: build_tree, update_tree, query_tree.

**Building tree:**To init the tree segments or intervals values

**Update tree:**To update value of an interval or segment

**Query tree:**To retrieve the value of an interval or segment

**Example Segment Tree:**

- The first node will hold the information for the interval
**[i, j]** - If i<j the left and right son will hold the information for the intervals
**[i, (i+j)/2]**and**[(i+j)/2+1, j]**

**N**elements is

**[logN] + 1**. Here is how a segment tree for the interval

**[0, 9]**would look like:

**Order of growth of segment trees operations**

**build_tree:**O(N lg(N))**update_tree:**O(lg(N + k))**query_tree:**O(lg(N + k))

K = Number of retrieved intervals or segments

**Show me your code**

**Lazy Propagation**

Sometimes

**a segment tree operation wouldn't survive if the problem constraints is too large, here it come lazy propagation along with the segment tree.**In the current version when we update a range, we branch its childs even if the segment is covered within range. In the lazy version we only mark its child that it needs to be updated and update it when needed.

Note: Read my solution for problem Can you answer these queries I in this article.

Note: Read my solution for problem Can you answer these queries I in this article.

**Sample Problems to try****References**