Implementácia

Oproti obyčajnému intervalovému stromu potrebujeme urobiť nasledovné zmeny:

Pre každý vrchol (okrem listov) si potrebujeme pamätať hodnotu, ktorú má daný úradník v diári (prípadne, že tam nič nemá). To, že úradník nemá v diári žiadnu hodnotu môžeme reprezentovať tak, že tam bude mať hodnotu $1$ — násobenie jednotkou s prvkami nič nerobí. Pre jednoduchšiu implementáciu môžeme dať diáre aj listom — budú si do nich občas niečo písať ale aj tak to nikdy nevyužijú. Asymptotickú časovú zložitosť nám to nezhorší.
Vždy, keď ide nejaký vrchol delegovať robotu na svojich synov, musí si skontrolovať, či má niečo v diári (a prípadne im o tom dať vedieť). Na tento účel si môžeme implementovať špeciálnu funkciu propagate(). Keďže synovia by si aj tak iba aktualizovali hodnoty a zapísali požiadavku do diára, nemusíme na nich volať

funkciu určenú na menenie intervalov, ale hodnoty a diáre im môžeme zmeniť priamo my. * Musíme implementovať funkciu na vyhodnocovanie tretieho druhu požiadaviek. To by malo byť pomerne priamočiare.

Keďže vďaka lazy propagation vieme zmeniť interval, nemusíme implementovať zmenu jednotlivých prvkov tak, ako pri štandardnom intervalovom strome. Väčšina kódu až na metódy update a propagate ostáva oproti nelenivému intervalovému stromu nezmenená.

import math

class LazySegmentTree:

    # vytvor intervalovy strom z daneho pola p
    def __init__(self, p):
        self.n = 2 ** math.ceil(math.log2(len(p)))
        self.values = [0] * (2 * self.n)
        self.lazy = [1] * (2 * self.n)
        for i in range(len(p)):
            self.values[i + self.n] = p[i]
        for i in range(self.n - 1, 0, -1):
            self.values[i] = self.values[i * 2] + self.values[i * 2 + 1]

    # sucet na intervale
    def query(self, v, i, j, l, r):
        if l >= j or r <= i:
            return 0
        if l <= i and r >= j:
            return self.values[v]
        self.propagate(v)
        mid = (i + j) // 2
        return self.query(v * 2, i, mid, l, r) + self.query(v * 2 + 1, mid, j, l, r)

    # prenasobenie hodnot na intervale hodnotou h
    def update(self, v, i, j, l, r, x):
        if l >= j or r <= i:
            return
        if l <= i and r >= j:
            self.lazy[v] *= x
            self.values[v] *= x
            return

        self.propagate(v)
        mid = (i + j) // 2
        self.update(v * 2, i, mid, l, r, x)
        self.update(v * 2 + 1, mid, j, l, r, x)
        self.values[v] = self.values[v * 2] + self.values[v * 2 + 1]

    # metoda, ktora synom posunie poziadavky, ktore im mali prist uz skor ale bol som lenivy
    def propagate(self, v):
        self.lazy[v * 2] *= self.lazy[v]
        self.values[v * 2] *= self.lazy[v]
        self.lazy[v * 2 + 1] *= self.lazy[v]
        self.values[v * 2 + 1] *= self.lazy[v]
        self.lazy[v] = 1