Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Segment Tree Basics
Search
halfrost
January 15, 2020
Programming
0
870
Segment Tree Basics
halfrost
January 15, 2020
Tweet
Share
More Decks by halfrost
See All by halfrost
Redis multi-data center two-way synchronization
halfrost
0
490
Redis design ideas and usage specifications
halfrost
0
370
Golang message streaming practice in Eleme
halfrost
0
350
SQL practical optimization
halfrost
0
340
Fundamentals of Cryptography
halfrost
0
260
The practice of spatial index in geographic service
halfrost
0
350
Getting started with Machine Learning
halfrost
0
250
Functional Reactive Programming
halfrost
0
270
Eleme Report
halfrost
1
330
Other Decks in Programming
See All in Programming
Honoの来た道とこれから
yusukebe
19
3k
From Subtype Polymorphism To Typeclass-based Ad hoc Polymorphism- An Example
philipschwarz
PRO
0
170
ピラミッド、アイスクリームコーン、SMURF: 自動テストの最適バランスを求めて / Pyramid Ice-Cream-Cone and SMURF
twada
PRO
9
1k
プロジェクト新規参入者のリードタイム短縮の観点から見る、品質の高いコードとアーキテクチャを保つメリット
d_endo
1
1k
Macとオーディオ再生 2024/11/02
yusukeito
0
180
Webの技術スタックで マルチプラットフォームアプリ開発を可能にするElixirDesktopの紹介
thehaigo
2
920
弊社の「意識チョット低いアーキテクチャ」10選
texmeijin
5
23k
macOS でできる リアルタイム動画像処理
biacco42
7
1.9k
推し活の ハイトラフィックに立ち向かう Railsとアーキテクチャ - Kaigi on Rails 2024
falcon8823
6
2.2k
飲食業界向けマルチプロダクトを実現させる開発体制とリアルな現状
hiroya0601
1
390
OpenTelemetryでRailsのパフォーマンス分析を始めてみよう(KoR2024)
ymtdzzz
4
1.6k
CSC509 Lecture 08
javiergs
PRO
0
110
Featured
See All Featured
Building an army of robots
kneath
302
42k
Gamification - CAS2011
davidbonilla
80
5k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
32
1.8k
A Philosophy of Restraint
colly
203
16k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
250
21k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
14
1.9k
A better future with KSS
kneath
238
17k
Visualization
eitanlees
144
15k
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
355
29k
Become a Pro
speakerdeck
PRO
24
5k
Build The Right Thing And Hit Your Dates
maggiecrowley
32
2.4k
Transcript
Segment Tree 基础篇
Range Minimum/Maximum Query •需求:在饿了么的⼀个⽤户的历史订单中,找出该⽤户指定⼀段 时间内单笔订单最贵/最便宜的订单 One problem •O(n), when query
K —> ∞ times ?
Range Minimum/Maximum Query •需求:在饿了么的⼀个⽤户的历史订单中,求出找出该⽤户指定 ⼀段时间内累积消费总⾦额 Another problem •O(n), when query
K —> ∞ times ? •prefixSum, time O(n), query O(1)
Range Minimum/Maximum Query •需求:在 12306 ⽹站上,统计⼀条线路上任意指定两个站点之间 的可售出的票数总和 One more thing
•O(n), when query K —> ∞ times ? •prefixSum, time O(n), update O(n), query O(1)
How to ? Range Minimum/Maximum Query 5 O(log n) or
O(1) ?
Presentation agenda 6 What How to use Leetcode example What
is segment tree 2 3 1 How Example
Define Segment Tree 7 1. ❌ Complete Binary Tree 2.
∈ Balanced Binary Tree 3. As Full binary tree
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)
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
How to create Segment Tree 10
How to query Segment Tree 11 ❗
How to update Segment Tree 12 ❗
How to update Segment Tree 13 •Update [2,3] ? •❌
O(n)
How to update Segment Tree 14 •Update [2,3] ? •✅O(log
n)
How to update Segment Tree 15
How to query Segment Tree 16 •push_down
How to update Segment Tree 17 •push_down + push_up
How to low space Segment Tree 18 •Leetcode 715
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)
Segment Tree 20 Example
Segment Tree 21 Example
Segment Tree 22 Example
Boyer-Moore Majority Vote Algorithm 23 Example
Segment Tree 24 Example
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
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
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