Square root decomposition
Nils Gustafsson
Vad är Sqrt-decomposition?
Vad är Sqrt-decomposition?
Vad är Sqrt-decomposition?
Vad är Sqrt-decomposition?
Intervallsummor
Givet är N tal och Q queries på formen
Intervallsummor
Givet är N tal och Q queries på formen
Lösning:
Naiv lösning: O(NQ)
Intervallsummor
Givet är N tal och Q queries på formen
Lösning:
Naiv lösning: O(NQ)
Segmentträd/Fenwickträd: O(Qlog(N))
Intervallsummor
Givet är N tal och Q queries på formen
Lösning:
Naiv lösning: O(NQ)
Segmentträd/Fenwickträd: O(Qlog(N))
SQRT-decomposition: O(Qsqrt(N))
Intervallsummor
Dela in intervallet i block av storlek B.
Håll koll på summan av alla tal i varje block.
Intervallsummor
Dela in intervallet i block av storlek B.
Håll koll på summan av alla tal i varje block.
Intervallsummor
Dela in intervallet i block av storlek B.
Håll koll på summan av alla tal i varje block.
Antal operationer: 2B + N/B
Intervallsummor
Hur sköter vi uppdateringarna?
Intervallsummor
Hur sköter vi uppdateringarna?
Räkna om all information i uppdateringens block:
Intervallsummor
Specialfall: intervallet är helt inuti ett block.
Intervallsummor
Givet är N tal och Q queries på formen
Intervallsummor
Givet är N tal och Q queries på formen
sum
lazy_set
lazy_sum
Mo’s algoritm
Mo’s algoritm
https://codeforces.com/problemset/problem/86/D
Givet är N tal och Q intervall.
För varje intervall:
Låt Kx vara antalet gånger talet x förekommer i intervallet. Räkna ut summan av Kx2 x.
Mo’s algoritm
https://codeforces.com/problemset/problem/86/D
Givet är N tal och Q intervall.
För varje intervall:
Låt Kx vara antalet gånger talet x förekommer i intervallet. Räkna ut summan av Kx2 x.
3 2 4 4 2 3 1 2 5 2 3 1 1 2 4 5 2 3
3*3*1 + 2*2*2 + 2*2*3 + 1*1*5 = 34
Mo’s algoritm
Vi behöver veta hur många gånger varje tal förekommer, men det är svårt att kombinera ihop den informationen mellan intervall.
3 2 4 4 2 3 1 2 5 2 3 1 1 2 4 5 2 3
F = [0, 3, 2, 2, 0, 1], ans = 34
Mo’s algoritm
Vi behöver veta hur många gånger varje tal förekommer, men det är svårt att kombinera ihop den informationen mellan intervall.
Däremot kan vi lätt expandera/krympa ett intervall i O(1).
3 2 4 4 2 3 1 2 5 2 3 1 1 2 4 5 2 3
F = [0, 3, 2, 2, 0, 1], ans = 34
Mo’s algoritm
Vi behöver veta hur många gånger varje tal förekommer, men det är svårt att kombinera ihop den informationen mellan intervall.
Däremot kan vi lätt expandera/krympa ett intervall i O(1).
3 2 4 4 2 3 1 2 5 2 3 1 1 2 4 5 2 3
F = [0, 3, 3, 2, 0, 1], ans = 44
F[2] += 1
Mo’s algoritm
Vi behöver veta hur många gånger varje tal förekommer, men det är svårt att kombinera ihop den informationen mellan intervall.
Däremot kan vi lätt expandera/krympa ett intervall i O(1).
3 2 4 4 2 3 1 2 5 2 3 1 1 2 4 5 2 3
F = [0, 3, 3, 1, 0, 1], ans = 35
F[3] -= 1
Mo’s algoritm
Lösning: Håll koll på ändpunkterna och “vandra” förbi alla intervall. Att vandra från [L1, R1] till [L2, R2] tar |L1-L2| + |R1-R2| steg.
3 2 4 4 2 3 1 2 5 2 3 1 1 2 4 5 2 3
Mo’s algoritm
Lösning: Håll koll på ändpunkterna och “vandra” förbi alla intervall. Att vandra från [L1, R1] till [L2, R2] tar |L1-L2| + |R1-R2| steg.
Det tar fortfarande O(NQ) i värsta fall. Kan vi besöka intervallen i en ordning som gör att går snabbare?
3 2 4 4 2 3 1 2 5 2 3 1 1 2 4 5 2 3
Mo’s algoritm
Dela in intervallet i block av storlek B. Sortera intervallen med avseende på:
Mo’s algoritm
Dela in intervallet i block av storlek B. Sortera intervallen med avseende på:
Mo’s algoritm
Dela in intervallet i block av storlek B. Sortera intervallen med avseende på:
Mo’s algoritm
Dela in intervallet i block av storlek B. Sortera intervallen med avseende på:
Mo’s algoritm
Dela in intervallet i block av storlek B. Sortera intervallen med avseende på:
Mo’s algoritm
Dela in intervallet i block av storlek B. Sortera intervallen med avseende på:
Vänsterändpunkterna färdas högst B mellan par av intervall, totalt QB.
Högerändpunkterna färdas N för varje block, totalt N2/B.
Mo’s algoritm
Dela in intervallet i block av storlek B. Sortera intervallen med avseende på:
Vänsterändpunkterna färdas högst B mellan par av intervall, totalt QB.
Högerändpunkterna färdas N för varje block, totalt N2/B.
Mo’s algoritm
Antal steg mellan två intervall |L1-L2| + |R1-R2| är manhattanavståndet mellan punkterna (L1, R1) och (L2, R2):
Mo’s algoritm
Antal steg mellan två intervall |L1-L2| + |R1-R2| är manhattanavståndet mellan punkterna (L1, R1) och (L2, R2):
Räkna trianglar
Räkna trianglar
Givet en graf med N noder och M kanter, räkna hur många trianglar det finns i grafen.
N,M <= 105.
Räkna trianglar
Givet en graf med N noder och M kanter, räkna hur många trianglar det finns i grafen.
N,M <= 105.
Först, lagra alla kanter i en hashtabell (unordered_set) så att vi snabbt kan kolla upp om ett par av noder har en kant.
Loopa sedan igenom alla par av grannar för varje nod.
Varje triangel räknas då 3 gånger.
Räkna trianglar
Givet en graf med N noder och M kanter, räkna hur många trianglar det finns i grafen.
N,M <= 105.
Först, lagra alla kanter i en hashtabell (unordered_set) så att vi snabbt kan kolla upp om ett par av noder har en kant.
Loopa sedan igenom alla par av grannar för varje nod.
Varje triangel räknas då 3 gånger.
Räkna trianglar
Problemet är noder med väldigt många grannar. Men det finns inte så många såna noder...
Räkna trianglar
Problemet är noder med väldigt många grannar. Men det finns inte så många såna noder…
Ta bara noder med och kör den förra lösningen. Antalet iterationer
är som störst när noder har grad dvs.
Räkna trianglar
Problemet är noder med väldigt många grannar. Men det finns inte så många såna noder…
Ta bara noder med och kör den förra lösningen. Antalet iterationer
är som störst när noder har grad dvs.
3
2
1
0
Räkna trianglar
På det här sättet kan vi räkna alla trianglar med minst en “lätt” nod som hörn, men vi missar alla trianglar med tre “tunga” noder…
Men det finns bara noder med fler än grannar!
Vi kan kolla alla tripplar med såna noder:
0
Dynamic connectivity
Dynamic connectivity
Givet är en graf med N noder och M kanter, och Q queries på formen:
Dynamic connectivity
Dela in alla queries i block av storlek .
Dynamic connectivity
Dela in alla queries i block av storlek .
I början av varje block, bygg ihop hela grafen i linjär tid.
Dynamic connectivity
Dela in alla queries i block av storlek .
I början av varje block, bygg ihop hela grafen i linjär tid.
För varje block, tjuvkika på alla queries i det blocket. Markera alla noder som deltar i någon av dessa. Det finns bara såna noder.
Dynamic connectivity
Dynamic connectivity
Komprimerad graf med storlek
Dynamic connectivity
Dela in alla queries i block av storlek .
I början av varje block, kolla på alla queries i det blocket och bygg ihop den komprimerade grafen.
För varje query, sök i den komprimerade grafen med DFS.