Варианты дерева Фенвика - История изменений

Ctrlalt: /* Двумерное дерево Фенвика */

2023-02-02T02:34:14Z

Двумерное дерево Фенвика

← Предыдущая версия		Версия от 02:34, 2 февраля 2023
Строка 97:		Строка 97:
	}		}

	void modify(int y, int x, int val) {		void modify(int cellY, int cellX, int val) {
	for (; y < f.size(); y \|= y + 1)		for (int y = cellY; y < f.size(); y \|= y + 1)
	for (; x < f[0].size(); x \|= x + 1)		for (int x = cellX; x < f[0].size(); x \|= x + 1)
	f[y][x] += val;		f[y][x] += val;
	}		}

Ctrlalt в 00:04, 31 августа 2021

2021-08-31T00:04:22Z

← Предыдущая версия		Версия от 00:04, 31 августа 2021
Строка 1:		Строка 1:
	== Одномерное дерево Фенвика ==		== Одномерное дерево Фенвика ==

	int f~~[MAX_SIZE]~~;		struct BIT {
			vector<int> f;

	~~int query~~(int r) {		BIT(int size) : f(size) {}
	~~int res = 0;~~
	~~for~~ (~~int i = r; i >= 0; i = (i & (i + 1~~)~~) - 1)~~
	~~res += f[i];~~
	~~return res;~~
	}

	void modify(int r, int val) {		int query(int r) {
	for (~~int i = r~~; i < ~~MAX_SIZE~~; i \|= i + 1)		int res = 0;
	f[i] += val;		for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
	}		res += f[i];
			return res;
			}

			void modify(int i, int val) {
			for (; i < f.size(); i \|= i + 1)
			f[i] += val;
			}
			};

	=== Запрос суммы на отрезке, изменение отдельных элементов ===		=== Запрос суммы на отрезке, изменение отдельных элементов ===
	query(r) ~~—~~ сумма элементов от 0-го до r-го.		t.query(r) — сумма элементов от 0-го до r-го.

	~~int prefixSum(int r)~~ {		struct BITRangeSumPointAdd {
	~~return query(r)~~;		BIT t;
	}

	void add(int ~~pos~~, int val) {		BITRangeSumPointAdd(int size) : t(size) {}
	modify(~~pos~~, val);
	}		int sum(int r) {
			return t.query(r);
			}

			int sum(int l, int r) {
			return sum(r) - (l ? sum(l - 1) : 0);
			}

			void add(int i, int val) {
			t.modify(i, val);
			}
			};

	=== Запрос значений отдельных элементов, изменение на отрезке ===		=== Запрос значений отдельных элементов, изменение на отрезке ===
	query(r) ~~—~~ значение r-го элемента.		t.query(i) — значение i-го элемента.

	~~int get(int pos)~~ {		struct BITPointSumRangeAdd {
	~~return query(pos)~~;		BIT t;
	}

	void add(int l, int r, int val) {		BITPointSumRangeAdd(int size) : t(size) {}
	modify(l, val);
	modify(r + 1, -val);		int get(int i) {
	}		return t.query(i);
			}

			void add(int l, int r, int val) {
			t.modify(l, val);
			t.modify(r + 1, -val);
			}
			};

	=== Запрос суммы на отрезке, изменение на отрезке ===		=== Запрос суммы на отрезке, изменение на отрезке ===
	Tx.query(r) * r + T.query(r) ~~—~~ сумма элементов от 0-го до r-го.		tx.query(r) * r + t.query(r) — сумма элементов от 0-го до r-го.
	[[Файл:fenwick_range_1d.png\|thumb\|right\|360px]]		[[Файл:fenwick_range_1d.png\|thumb\|right\|360px]]
	int ~~prefixSum~~(int r) {		struct BITRangeSumRangeAdd {
	return Tx.query(r) * r + T.query(r);		BIT t, tx;
	}
			BITRangeSumRangeAdd(int size) : t(size), tx(size) {}

			int sum(int r) {
			return tx.query(r) * r + t.query(r);
			}

			int sum(int l, int r) {
			return sum(r) - (l ? sum(l - 1) : 0);
			}

	void add(int l, int r, int val) {		void add(int l, int r, int val) {
	Tx.modify(l, val);		tx.modify(l, val);
	Tx.modify(r + 1, -val);		tx.modify(r + 1, -val);
	T.modify(l, val * (-l + 1));		t.modify(l, val * (-l + 1));
	T.modify(r + 1, val * r);		t.modify(r + 1, val * r);
	}		}
			};

	== Двумерное дерево Фенвика ==		== Двумерное дерево Фенвика ==

Ctrlalt в 23:52, 30 августа 2021

2021-08-30T23:52:54Z

Внесённые изменения

Ctrlalt: /* Запрос суммы на прямоугольнике, изменение на прямоугольнике */

2021-08-30T23:28:37Z

Запрос суммы на прямоугольнике, изменение на прямоугольнике

← Предыдущая версия		Версия от 23:28, 30 августа 2021
Строка 96:		Строка 96:

	=== Запрос суммы на прямоугольнике, изменение на прямоугольнике ===		=== Запрос суммы на прямоугольнике, изменение на прямоугольнике ===
	Tyx.query(ry, rx) * x * y + Ty.query(ry, rx) * y + Tx.query(ry, rx) * x + T.query(ry, rx) — сумма элементов от (0; 0)-го до (ry; rx)-го.		Tyx.query(ry, rx) * ry * rx + Ty.query(ry, rx) * ry + Tx.query(ry, rx) * rx + T.query(ry, rx) — сумма элементов от (0; 0)-го до (ry; rx)-го.
	[[Файл:fenwick_range_2d.png\|thumb\|right\|360px]]		[[Файл:fenwick_range_2d.png\|thumb\|right\|360px]]
	int prefixSum(int ry, int rx) {		int prefixSum(int ry, int rx) {
	return Tyx.query(ry, rx) * x * y + Ty.query(ry, rx) * y + Tx.query(ry, rx) * x + T.query(ry, rx);		return Tyx.query(ry, rx) * ry * rx + Ty.query(ry, rx) * ry + Tx.query(ry, rx) * rx + T.query(ry, rx);
	}		}

Ctrlalt: /* Двумерное дерево Фенвика */

2021-08-30T23:22:12Z

Двумерное дерево Фенвика

← Предыдущая версия		Версия от 23:22, 30 августа 2021
Строка 60:		Строка 60:
	for (int i = ry; i >= 0; i = (i & (i + 1)) - 1)		for (int i = ry; i >= 0; i = (i & (i + 1)) - 1)
	for (int j = rx; j >= 0; j = (j & (j + 1)) - 1)		for (int j = rx; j >= 0; j = (j & (j + 1)) - 1)
	res += f[ry][rx];		res += f[i][j];
	return res;		return res;
	}		}
Строка 119:		Строка 119:

	T.modify(ly, lx, val * (-lx + 1) * (-ly + 1));		T.modify(ly, lx, val * (-lx + 1) * (-ly + 1));
	T.modify(ry + 1, lx val * (-lx + 1) * ry);		T.modify(ry + 1, lx, val * (-lx + 1) * ry);
	T.modify(ly, rx + 1, val * rx * (-ly + 1));		T.modify(ly, rx + 1, val * rx * (-ly + 1));
	T.modify(ry + 1, rx + 1, val * rx * ry);		T.modify(ry + 1, rx + 1, val * rx * ry);

Ctrlalt в 23:34, 22 июня 2016

2016-06-22T23:34:53Z

Внесённые изменения

Ctrlalt: /* Запрос суммы на прямоугольнике, изменение на прямоугольнике */

2014-11-17T12:48:24Z

Запрос суммы на прямоугольнике, изменение на прямоугольнике

← Предыдущая версия		Версия от 12:48, 17 ноября 2014
Строка 97:		Строка 97:
	=== Запрос суммы на прямоугольнике, изменение на прямоугольнике ===		=== Запрос суммы на прямоугольнике, изменение на прямоугольнике ===
	<tt>delta(x, y) * x * y + gamma(x, y) * y + beta(x, y) * x + alpha(x, y)</tt> — сумма элементов от <tt>(0; 0)</tt>-го до <tt>(x; y)</tt>-го.		<tt>delta(x, y) * x * y + gamma(x, y) * y + beta(x, y) * x + alpha(x, y)</tt> — сумма элементов от <tt>(0; 0)</tt>-го до <tt>(x; y)</tt>-го.
			[[Файл:fenwick_range_2d.png\|thumb\|right\|360px]]
	int sum(int x, int y) {		int sum(int x, int y) {
	return delta(x, y) * x * y + gamma(x, y) * y + beta(x, y) * x + alpha(x, y);		return delta(x, y) * x * y + gamma(x, y) * y + beta(x, y) * x + alpha(x, y);

Ctrlalt: /* Запрос суммы на отрезке, изменение на отрезке */

2014-11-17T12:47:11Z

Запрос суммы на отрезке, изменение на отрезке

← Предыдущая версия		Версия от 12:47, 17 ноября 2014
Строка 40:		Строка 40:
	=== Запрос суммы на отрезке, изменение на отрезке ===		=== Запрос суммы на отрезке, изменение на отрезке ===
	<tt>beta(x) * x + alpha(x)</tt> — сумма элементов от <tt>0</tt>-го до <tt>x</tt>-го.		<tt>beta(x) * x + alpha(x)</tt> — сумма элементов от <tt>0</tt>-го до <tt>x</tt>-го.
			[[Файл:fenwick_range_1d.png\|thumb\|right\|360px]]
	int sum(int x) {		int sum(int x) {
	return beta(x) * x + alpha(x);		return beta(x) * x + alpha(x);
Строка 50:		Строка 50:
	modifyBetas(r + 1, -val);		modifyBetas(r + 1, -val);
	modifyAlphas(r + 1, val * r);		modifyAlphas(r + 1, val * r);
	}		}

	== Двумерное дерево Фенвика ==		== Двумерное дерево Фенвика ==

Ctrlalt: /* Двумерное дерево Фенвика */

2014-11-14T19:22:46Z

Двумерное дерево Фенвика

← Предыдущая версия		Версия от 19:22, 14 ноября 2014
Строка 66:		Строка 66:
	void modifyAlphas(int x, int y, int val) {		void modifyAlphas(int x, int y, int val) {
	for (int i = x; i < MAX_SIZE; i \|= i + 1)		for (int i = x; i < MAX_SIZE; i \|= i + 1)
	for (int j = x; j < MAX_SIZE; j \|= j + 1)		for (int j = y; j < MAX_SIZE; j \|= j + 1)
	a[i][j] += val;		a[i][j] += val;
	}		}

Ctrlalt: /* Двумерное дерево Фенвика */

2014-11-14T15:07:50Z

Двумерное дерево Фенвика

← Предыдущая версия		Версия от 15:07, 14 ноября 2014
Строка 66:		Строка 66:
	void modifyAlphas(int x, int y, int val) {		void modifyAlphas(int x, int y, int val) {
	for (int i = x; i < MAX_SIZE; i \|= i + 1)		for (int i = x; i < MAX_SIZE; i \|= i + 1)
	for (int i = x; i < MAX_SIZE; i \|= i + 1)		for (int j = x; j < MAX_SIZE; j \|= j + 1)
	a[i][j] += val;		a[i][j] += val;
	}		}
Строка 122:		Строка 122:
	modifyBetas(rx + 1, ry + 1, -val * ry);		modifyBetas(rx + 1, ry + 1, -val * ry);
	modifyAlphas(rx + 1, ry + 1, val * rx * ry);		modifyAlphas(rx + 1, ry + 1, val * rx * ry);
	}		}

	== Ссылки ==		== Ссылки ==