Velik broj srednjoškolskih natjecatelja zna logaritamsku strukturu (binary indexed tree ili Fenwickovo stablo) koje služi da bismo brzo provodili operacije oblika “promijeni K-ti element niza” i “odredi min/max/sumu nekog prefiksa niza”.

Manje ljudi zna da logaritamska može podržati i promjenu na nekom intervalu niza (povećaj elemente od A-tog do B-tog za V). Ovdje možete vidjeti kako to učiniti s logaritamskom. Bilo bi zanimljivo napraviti usporedbu duljine i efikasnosti tog rješenja u odnosu na rješenje s tournament stablom (segment tree).

(Koliko ja znam, logaritamskom nije moguće podržati i efikasno postavljanje cijelog intervala na neki broj. Ispravite me ako griješim.)

Postoji i 2D logaritamska koja opisuje matricu umjesto niza. Ona se također može prilagoditi tako da podržava intervalne promjene; evo odgovarajuće implementacije (Vilim Lendvaj, IOI pripreme 2016.):

struct fenwick
{
long long data[MAXN][MAXN];

void update(int i, int j, llint x)
{
for (; i <= n; i += i&-i)
for (int j2 = j; j2 <= n; j2 += j2&-j2)
data[i][j2] += x;
}

long long query(int i, int j)
{
long long x = 0;
for (; 0 < i; i -= i&-i)
for (int j2 = j; 0 < j2; j2 -= j2&-j2)
x += data[i][j2];

return x;
}
} fen1, fenI, fenJ, fenIJ;

long long query(int i, int j)
{
return fenIJ.query(i, j) * i * j + fenI.query(i, j) * i + fenJ.query(i, j) * j + fen1.query(i, j);
}

void update(int i1, int j1, int i2, int j2, long long x)
{
fenIJ.update(i1, j1, x);
fenIJ.update(i1, j2 + 1, -x);
fenIJ.update(i2 + 1, j1, -x);
fenIJ.update(i2 + 1, j2 + 1, x);

fenI.update(i1, j1, -x * (j1 - 1));
fenI.update(i1, j2 + 1, x * j2);
fenI.update(i2 + 1, j1, x * (j1 - 1));
fenI.update(i2 + 1, j2 + 1, -x * j2);

fenJ.update(i1, j1, -x * (i1 - 1));
fenJ.update(i1, j2 + 1, x * (i1 - 1));
fenJ.update(i2 + 1, j1, x * i2);
fenJ.update(i2 + 1, j2 + 1, -x * i2);

fen1.update(i1, j1, x * (i1 - 1) * (j1 - 1));
fen1.update(i1, j2 + 1, -x * (i1 - 1) * j2);
fen1.update(i2 + 1, j1, -x * i2 * (j1 - 1));
fen1.update(i2 + 1, j2 + 1, x * i2 * j2);
}

long long query(int i1, int j1, int i2, int j2)
{
return query(i2, j2) - query(i2, j1 - 1) - query(i1 - 1, j2) + query(i1 - 1, j1 - 1);
}

Eventualne optimizacije su dobrodošle.

Zadatak: https://www.codechef.com/DCL1501/problems/DCL2015E/