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
500
Redis design ideas and usage specifications
halfrost
0
370
Golang message streaming practice in Eleme
halfrost
0
360
SQL practical optimization
halfrost
0
350
Fundamentals of Cryptography
halfrost
0
270
The practice of spatial index in geographic service
halfrost
0
350
Getting started with Machine Learning
halfrost
0
250
Functional Reactive Programming
halfrost
0
280
Eleme Report
halfrost
1
330
Other Decks in Programming
See All in Programming
subpath importsで始めるモック生活
10tera
0
340
WebフロントエンドにおけるGraphQL(あるいはバックエンドのAPI)との向き合い方 / #241106_plk_frontend
izumin5210
4
1.4k
WebAssembly Unleashed: Powering Server-Side Applications
chrisft25
0
130
as(型アサーション)を書く前にできること
marokanatani
10
2.8k
[Do iOS '24] Ship your app on a Friday...and enjoy your weekend!
polpielladev
0
120
Contemporary Test Cases
maaretp
0
140
OnlineTestConf: Test Automation Friend or Foe
maaretp
0
120
Jakarta EE meets AI
ivargrimstad
0
800
みんなでプロポーザルを書いてみた
yuriko1211
0
290
React CompilerとFine Grained Reactivityと宣言的UIのこれから / The next chapter of declarative UI
ssssota
5
560
Functional Event Sourcing using Sekiban
tomohisa
0
110
Why Jakarta EE Matters to Spring - and Vice Versa
ivargrimstad
0
1.3k
Featured
See All Featured
Building Flexible Design Systems
yeseniaperezcruz
327
38k
How to train your dragon (web standard)
notwaldorf
88
5.7k
How GitHub (no longer) Works
holman
310
140k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
159
15k
Producing Creativity
orderedlist
PRO
341
39k
What’s in a name? Adding method to the madness
productmarketing
PRO
22
3.1k
Speed Design
sergeychernyshev
25
620
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
27
4.3k
Save Time (by Creating Custom Rails Generators)
garrettdimon
PRO
27
840
jQuery: Nuts, Bolts and Bling
dougneiner
61
7.5k
Typedesign – Prime Four
hannesfritz
40
2.4k
What's new in Ruby 2.0
geeforr
343
31k
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