Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Segment Tree Basics

halfrost
January 15, 2020

Segment Tree Basics

halfrost

January 15, 2020
Tweet

More Decks by halfrost

Other Decks in Programming

Transcript

  1. Define Segment Tree 7 1. ❌ Complete Binary Tree 2.

    ∈ Balanced Binary Tree 3. As Full binary tree
  2. How many node Segment Tree 8 0-level : 1 1-level

    : 2 2-level : 4 3-level : 8 4-level : 16 (n-1)—level :2^(n-1) n-level:2^n Σ 0-(n-1) level:Σ = 2^n - 1 ≈ n-level => 2n Mathematical Induction:Σ = 4n (n = 2^k or n = 2^k + 1)
  3. How many node Segment Tree 9 •When n≥3, [1,n] segment

    split [1,n] into 2*⌊log (n-1)⌋ sub- Interval •4n ≥ 2*⌊log (n-1)⌋ <= 2n ≥ log (n-1) <= 4^n ≥ n-1
  4. Compared ST VS Array 19 20% 80% 60% 40% 2585

    785 Update: Array O(n) | Segment Tree O(log n) Query: Array O(n) | Segment Tree O(log n)
  5. Segment Tree 25 Example •judge threshold •count = map[1:[0 1

    4 5] 2:[2 3]] •eg: 1 in [0,5] count , twice binary search, find [lowerBound, upperBound) •(upperBound - lowerBound) ≥ threshold
  6. Segment Tree 26 •Leetcode 327. Count of Range Sum •Leetcode

    715. Range Module •Leetcode 699. Falling Squares & 732. My Calendar III •Leetcode 850. Rectangle Area II •Leetcode 218. The Skyline Problem Exercise
  7. Advance 27 15% 35% 50% •One point update (update: min/change,

    query: sum/min) •Interval update (update: min/change, query: sum/hash) •Discretization •Interval merge •Scan line •Binary Index Tree