Segment Tree Beats

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)$.