Segment tree beats on tekniikka, jolla voi ratkaista seuraavantyyppisiä datastruktuuriongelmia:
Kaikissa ongelmissa x_i, 1 \leq i \leq n on taulukko, jonka alkuarvot on annettu, ja pitää tukea listattuja operaatiota.
Ongelma 1:
- Annettuna l, r, v, aseta x_i \leftarrow \max(x_i, v) kaikille l \leq i \leq r
- Annettuna l, r, palauta \sum_{i = l}^{r} x_i
Ongelma 2:
- Annettuna l, r, v, aseta x_i \leftarrow v kaikille l \leq i \leq r
- Annettuna l, r, v, aseta x_i \leftarrow (x_i \text{ mod } v) kaikille l \leq i \leq r
- Annettuna l, r, palauta \sum_{i = l}^{r} x_i
Ongelma 3:
- Annettuna l, r, v, aseta x_i \leftarrow \max(x_i, v) kaikille l \leq i \leq r
- Annettuna l, r, v, aseta x_i \leftarrow x_i + v
- Annettuna l, r, palauta \sum_{i = l}^{r} x_i
Ongelma 1 ratkeaa ajassa \mathcal{O}(n \log n), ongelma 2 ajassa \mathcal{O}(n \log n \log v), missä v on suurin mahdollinen arvo, ja ongelma 3 ajassa \mathcal{O}(n \log^2 n).
Ideana on muokata standardikoodia laiskalle segmenttipuulle. Seuraava koodi tekee operaation välille [a, b):
void rangeApply(int a, int b, int v, int i, int ia, int ib) {
if (b <= ia || ib <= a) return;
if (a <= ia && ib <= b) apply(i, v);
else {
int mid = (ia + ib) / 2;
rangeApply(a, b, v, 2*i, ia, mid);
rangeApply(a, b, v, 2*i+1, mid, ib);
update(i);
}
}
Haluamme korvata ehdon
b <= ia || ib <= a
voimakkaammalla ehdolla, ja ehdon
a <= ia && ib <= b
heikommalla ehdolla.
Esimerkiksi ensimmäisessä ongelmassa, korvaamme ensimmäisen ehdon ehdolla
a <= ib || b <= ia || interval_min[i] >= v
ja toisen ehdolla
a <= ia && ib <= b && interval_second_min[i] > v.
Tässä interval_second_min[i] on välin pienin arvo, joka on aidosti suurempi kuin interval_min[i].
Käytämme vastaavia ehtoja myös toisessa ongelmassa: muutamme ensimmäiseksi ehdoksi
a <= ib || b <= ia || interval_max[i] < v
ja toiseksi ehdoksi
a <= ia && ib <= b && interval_second_max[i] < v.
Ideana on se, että kun kutsumme apply-funktiota, alipuussa johon sitä kutsumme, on vain yhtä arvoa johon operaatio vaikuttaa! Jos tiedämme kuinka monta kertaa tämä arvo esiintyy alipuussa, voimme helposti päivittää välin summan.
Ratkaisun aikavaatimus voidaan todistaa potentiaalifunktiolla. Otetaan seuraava esimerkkitaulukko:
Ensimmäisessä tehtävässä käytämme potentiaalifunktiona arvoa \log n \cdot c, missä c on niiden solmujen määrä segmenttipuussa, missä solmua vastaavan välin minimi on isompi kuin solmun vanhemman välin minimi. Koska c \leq n, potentiaalifunktion arvo alussa on enintään \mathcal{O}(n \log n), ja jokainen operaatio kasvattaa sitä enintään \mathcal{O}(\log n).
Tässä taulukon välien minimit:
Ja solmut, jotka kontributoivat arvoon c:
Olkoon f(x) pienin epänegatiivinen kokonaisluku, jolla \left\lfloor \frac{x}{2^{f(x)}} \right\rfloor = 0. Olkoon f(S) = \sum_{x \in S} f(x) joukoilla S. Olkoon T_i joukko arvoista solmun i alipuussa, missä jokainen arvo esiintyy enintään kerran. Toisessa tehtävässä käytämme potentiaalina arvoa \sum_{i} \mathbb{I}[|T_{i}| > 1] f(T_i). Potentiaalifunktion arvo alussa on enintään \mathcal{O}(n \log n \log v), ja jokainen operaatio kasvattaa sitä enintään \mathcal{O}(\log n \log v).
Kolmannessa tehtävässä toimii sama potentiaalifunktio kuin ensimmäisessä, mutta välin kasvatus voi kasvattaa potentiaalia \mathcal{O}(\log^2 n).