Tip of the day: logaritamska++

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/

2 misli o “Tip of the day: logaritamska++

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava /  Izmijeni )

Google+ photo

Ovaj komentar pišete koristeći vaš Google+ račun. Odjava /  Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava /  Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava /  Izmijeni )

Spajanje na %s