1. Introduction To Segment Tree #

Created Saturday 25 July 2020

• Segment trees are used when two conditions are met:
  1. Range queries - Return a value between two indexes, L and R in an array → O(R-L) naive method.
  2. Updates - values can be changed in the array. This update can change the range query answer → O(1) naive method.
• If queries are less the above method works, but if we have many queries, we need to store some values in order to answer the queries quickly, here O(1) is the query time. O(n) will be the updation.
• But if we queries and updates are equally frequent, then we use a data structure called a segment tree.
• **Segment Tree **is a binary tree used when both updates and queries are equally frequent. Here updates and queries are both O(log n) - a great data structure.
  • It is always balanced.
  • The leaf nodes are the values of the array.