Fenwick Tree, Range Updates

Fenwick Tree with Arrays, Range Updates

const int N = 100000;
int dataMul[N];
int dataAdd[N];

void internalUpdate(int at, int mul, int add) {
	for(int i=at; i<N ; i = (i|(i+1)) ) {
		dataMul[i] += mul;
		dataAdd[i] += add;
	}
}
void update(int left, int right, int it) {
	internalUpdate(left, it, -it*(left-1));
	internalUpdate(right, -it, it*right);
}

int querySum(int x) {
	int mul = 0, add = 0, start = x;
	for(int i=x; i>=0; i = (i&(i+1))-1 ) {
		mul += dataMul[i];
		add += dataAdd[i];
	}
	return mul * start + add;
}

int query(int x, int y) {
	return querySum(y) - querySum(x-1);
}

int main() {
	update(1, 1010, 1);
	update(100, 1010, 2);

	cout << query(1, 1010) << endl;
	cout << query(1010, 1010) << endl;
}

Fenwick Tree with Maps, Range Updates

const int N = 1<<30;
map<int, int> dataMul;
map<int, int> dataAdd;

void internalUpdate(int at, int mul, int add) {
	for(int i=at; i<N ; i = (i|(i+1)) ) {
		dataMul[i] += mul;
		dataAdd[i] += add;
	}
}
void update(int left, int right, int it) {
	internalUpdate(left, it, -it*(left-1));
	internalUpdate(right, -it, it*right);
}

int querySum(int x) {
	int mul = 0, add = 0, start = x;
	for(int i=x; i>=0; i = (i&(i+1))-1 ){
		if(dataMul.find(i) != dataMul.end())
			mul += dataMul[i];
		if(dataAdd.find(i) != dataAdd.end())
			add += dataAdd[i];
	}
	return mul * start + add;
}

int query(int x, int y) {
	return querySum(y) - querySum(x-1);
}

int main() {
	update(100000000, 100000010, 1);
	update(100, 100000010, 1);

	cout << query(109, 100000010) << endl;
	cout << query(100000010, 100000010) << endl;
}

Official post: http://petr-mitrichev.blogspot.com/2013/05/fenwick-tree-range-updates.html

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s