Segment Trees

Question 1

Segment Tree

Answer 1

• Binary tree
• Each element in original array is leaf of binary tree
• Allows you to ask questions about a range of indices in an array
• static data strcture – cannot be modified once built

Question 2

Segment Tee

Construction

Answer 2

• Elements of array should become leaves of tree
• Root is minimum of entire range
• Represented implicity with array (like binary heap)

Steps

1. Split array into halves recursively into array is size 2 and 1
2. Bubble up, recording minimums of elements in pairs
3. Create segment tree array using formula:
4. If array size is power of 2

size*2 - 1

If not

Find next power of 2

num*2 - 1

5. Initialize segment tree array to inf

Time: O(n)

Space: O(n)

Question 3

Segment Tree

Searching

Answer 3

• Describes the overlap of the query interval to the node itnervals

3 conditions

1. Total overlap
   
   • Node interval fits completely inside query interval
   • Stop, return value at node
2. No overlap/disjoint
   
   • Node interval and query interval are disjoint
   • Return max (really big number)
3. Partial overlap
   
   • Node interval not completely inside query interval
   • Basically not 1 or 2
   • Must check both sides

OlogN

Question 4

Segment Tree

Size

Answer 4

• If array size is power of 2
  
  • size*2 - 1
• If not
  
  • Find next power of 2
  • num*2 - 1
    *

Question 5

Segment Tree

range query

Answer 5

*

Question 6

Segment Tree

Lazy Propagation

Answer 6

• Increase the size of a range by increasing nodes
• Propogation only happens when nodes are visited

Steps

1. Find range nodes like normal
2. Increase val at node
3. Increase val during recursive return