Дерево отрезков - История изменений

Ctrlalt в 17:58, 18 февраля 2023

2023-02-18T17:58:45Z

← Предыдущая версия		Версия от 17:58, 18 февраля 2023
Строка 27:		Строка 27:

	struct SegmentTree {		struct SegmentTree {
			int size;
	vector<long long> t;		vector<long long> t;
	~~int size;~~

	void build(int v, int vl, int vr, vector<int> &a) {		void build(int v, int vl, int vr, vector<int> &a) {
Строка 47:		Строка 47:
	return t[v];		return t[v];
	int vm = vl + (vr - vl) / 2;		int vm = vl + (vr - vl) / 2;
	~~int~~ ql = query(2 * v + 1, vl, vm, l, r);		long long ql = query(2 * v + 1, vl, vm, l, r);
	~~int~~ qr = query(2 * v + 2, vm + 1, vr, l, r);		long long qr = query(2 * v + 2, vm + 1, vr, l, r);
	return ql + qr;		return ql + qr;
	}		}
Строка 66:		Строка 66:

	SegmentTree(vector<int> &a) :		SegmentTree(vector<int> &a) :
	size(a.size()), t~~(4 * a.size()), tAdd~~(4 * a.size()) {		size(a.size()), t(4 * a.size()) {
	build(0, 0, size - 1, a);		build(0, 0, size - 1, a);
	}		}
Строка 85:		Строка 85:

	struct SegmentTree {		struct SegmentTree {
			int size;
	vector<long long> t, tAdd;		vector<long long> t, tAdd;
	~~int size;~~

	void build(int v, int vl, int vr, vector<int> &a) {		void build(int v, int vl, int vr, vector<int> &a) {
Строка 117:		Строка 117:
	return t[v];		return t[v];
	int vm = vl + (vr - vl) / 2;		int vm = vl + (vr - vl) / 2;
	~~int~~ ql = query(2 * v + 1, vl, vm, l, r);		long long ql = query(2 * v + 1, vl, vm, l, r);
	~~int~~ qr = query(2 * v + 2, vm + 1, vr, l, r);		long long qr = query(2 * v + 2, vm + 1, vr, l, r);
	return ql + qr;		return ql + qr;
	}		}

Ctrlalt в 16:16, 22 декабря 2022

2022-12-22T16:16:15Z

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

Ctrlalt: /* Ссылки */

2020-08-21T05:12:58Z

Ссылки

← Предыдущая версия		Версия от 05:12, 21 августа 2020
Строка 182:		Строка 182:
	* [http://i.cs.hku.hk/~provinci/training2015/notes3.pdf i.cs.hku.hk — Segment Trees: Applications]		* [http://i.cs.hku.hk/~provinci/training2015/notes3.pdf i.cs.hku.hk — Segment Trees: Applications]
	* [http://sharmaeklavya2.github.io/blog/generalizing-segment-trees.html sharmaeklavya2.github.io — Generalizing Segment Trees]		* [http://sharmaeklavya2.github.io/blog/generalizing-segment-trees.html sharmaeklavya2.github.io — Generalizing Segment Trees]
			* [https://arxiv.org/pdf/1811.01226.pdf Ibtehaz N. Multidimensional segment trees can do range queries and updates in logarithmic time]
	Демонстрация:		Демонстрация:
	* [https://visualgo.net/en/segmenttree VisuAlgo — Segment Tree]		* [https://visualgo.net/en/segmenttree VisuAlgo — Segment Tree]

Ctrlalt: /* Ссылки */

2020-08-21T04:50:33Z

Ссылки

← Предыдущая версия		Версия от 04:50, 21 августа 2020
Строка 175:		Строка 175:
	== Ссылки ==		== Ссылки ==
	Теория:		Теория:
			* Codeforces EDU — Дерево отрезков: [https://codeforces.com/edu/course/2/lesson/4 часть 1], [https://codeforces.com/edu/course/2/lesson/5 часть 2]
	* [http://e-maxx.ru/algo/segment_tree e-maxx.ru — Дерево отрезков]		* [http://e-maxx.ru/algo/segment_tree e-maxx.ru — Дерево отрезков]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.BE.D1.82.D1.80.D0.B5.D0.B7.D0.BA.D0.BE.D0.B2 neerc.ifmo.ru/wiki — Дерево отрезков]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.BE.D1.82.D1.80.D0.B5.D0.B7.D0.BA.D0.BE.D0.B2 neerc.ifmo.ru/wiki — Дерево отрезков]
	* [https://brestprog.by/topics/segmenttree/ brestprog — Дерево отрезков]		* [https://brestprog.by/topics/segmenttree/ brestprog — Дерево отрезков]
	* Codeforces EDU — Дерево отрезков: [https://codeforces.com/edu/course/2/lesson/4 часть 1], [https://codeforces.com/edu/course/2/lesson/5 часть 2]
	* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/mipt-2014-burunduk1-ds.pdf Копелиович С. Лекция про структуры данных Зимней школы МФТИ]		* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/mipt-2014-burunduk1-ds.pdf Копелиович С. Лекция про структуры данных Зимней школы МФТИ]
	* [http://i.cs.hku.hk/~provinci/training2015/notes3.pdf i.cs.hku.hk — Segment Trees: Applications]		* [http://i.cs.hku.hk/~provinci/training2015/notes3.pdf i.cs.hku.hk — Segment Trees: Applications]

Ctrlalt: /* Ссылки */

2020-08-21T04:35:50Z

Ссылки

← Предыдущая версия		Версия от 04:35, 21 августа 2020
Строка 177:		Строка 177:
	* [http://e-maxx.ru/algo/segment_tree e-maxx.ru — Дерево отрезков]		* [http://e-maxx.ru/algo/segment_tree e-maxx.ru — Дерево отрезков]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.BE.D1.82.D1.80.D0.B5.D0.B7.D0.BA.D0.BE.D0.B2 neerc.ifmo.ru/wiki — Дерево отрезков]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.BE.D1.82.D1.80.D0.B5.D0.B7.D0.BA.D0.BE.D0.B2 neerc.ifmo.ru/wiki — Дерево отрезков]
	* [~~http~~://brestprog.~~neocities.org~~/~~lections~~/segmenttree~~.html~~ brestprog.~~neocities~~.~~org — Дерево отрезков~~]		* [https://brestprog.by/topics/segmenttree/ brestprog — Дерево отрезков]
			* Codeforces EDU — Дерево отрезков: [https://codeforces.com/edu/course/2/lesson/4 часть 1], [https://codeforces.com/edu/course/2/lesson/5 часть 2]
	* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/mipt-2014-burunduk1-ds.pdf Копелиович С. Лекция про структуры данных Зимней школы МФТИ]		* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/mipt-2014-burunduk1-ds.pdf Копелиович С. Лекция про структуры данных Зимней школы МФТИ]
	* [http://i.cs.hku.hk/~provinci/training2015/notes3.pdf i.cs.hku.hk — Segment Trees: Applications]		* [http://i.cs.hku.hk/~provinci/training2015/notes3.pdf i.cs.hku.hk — Segment Trees: Applications]
	* [http://sharmaeklavya2.github.io/blog/generalizing-segment-trees.html sharmaeklavya2.github.io — Generalizing Segment Trees]		* [http://sharmaeklavya2.github.io/blog/generalizing-segment-trees.html sharmaeklavya2.github.io — Generalizing Segment Trees]
	Демонстрация:		Демонстрация:
	* [~~http~~://visualgo.net/segmenttree~~.html~~ VisuAlgo ~~—~~ Segment Tree]		* [https://visualgo.net/en/segmenttree VisuAlgo — Segment Tree]
	Код:		Код:
	* [http://github.com/indy256/codelibrary/blob/9f99e9476b1435fb6ccaea6e1b83684bc5af3ef1/java/src/SegmentTree.java CodeLibrary — Segment Tree with interval modification]		* [http://github.com/indy256/codelibrary/blob/9f99e9476b1435fb6ccaea6e1b83684bc5af3ef1/java/src/SegmentTree.java CodeLibrary — Segment Tree with interval modification]

Ctrlalt: /* Ссылки */

2019-07-30T16:05:29Z

Ссылки

← Предыдущая версия		Версия от 16:05, 30 июля 2019
Строка 184:		Строка 184:
	* [http://visualgo.net/segmenttree.html VisuAlgo — Segment Tree]		* [http://visualgo.net/segmenttree.html VisuAlgo — Segment Tree]
	Код:		Код:
	* [http://~~www.sites.google~~.com~~/site~~/indy256/~~algo~~/~~segment_tree indy256 — Segment Tree with interval modification]~~		* [http://github.com/indy256/codelibrary/blob/9f99e9476b1435fb6ccaea6e1b83684bc5af3ef1/java/src/SegmentTree.java CodeLibrary — Segment Tree with interval modification]
	* [http://~~www.sites.google.com~~/~~site~~/~~indy256/algo/segment_tree_fast indy256~~ — Segment Tree with interval modification ~~without recursion~~]		* [http://github.com/indy256/codelibrary/blob/9f99e9476b1435fb6ccaea6e1b83684bc5af3ef1/java/src/SegmentTreeFast.java CodeLibrary — Segment Tree with interval modification without recursion]
	* [http://github.com/indy256/codelibrary/blob/~~master~~/~~cpp~~/~~structures~~/~~segment_tree~~.h CodeLibrary ~~—~~ Segment ~~tree~~]
	* [http://github.com/ADJA/algos/blob/master/DataStructures/SegmentTree(Assign-Sum).cpp Algos — Segment Tree (Assign-Sum)]		* [http://github.com/ADJA/algos/blob/master/DataStructures/SegmentTree(Assign-Sum).cpp Algos — Segment Tree (Assign-Sum)]
	* [http://github.com/ADJA/algos/blob/master/DataStructures/ImplicitSegmentTree.cpp Algos — Implicit segment tree]		* [http://github.com/ADJA/algos/blob/master/DataStructures/ImplicitSegmentTree.cpp Algos — Implicit segment tree]

Ctrlalt: /* Ссылки */

2019-07-30T11:28:26Z

Ссылки

← Предыдущая версия		Версия от 11:28, 30 июля 2019
Строка 180:		Строка 180:
	* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/mipt-2014-burunduk1-ds.pdf Копелиович С. Лекция про структуры данных Зимней школы МФТИ]		* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/mipt-2014-burunduk1-ds.pdf Копелиович С. Лекция про структуры данных Зимней школы МФТИ]
	* [http://i.cs.hku.hk/~provinci/training2015/notes3.pdf i.cs.hku.hk — Segment Trees: Applications]		* [http://i.cs.hku.hk/~provinci/training2015/notes3.pdf i.cs.hku.hk — Segment Trees: Applications]
			* [http://sharmaeklavya2.github.io/blog/generalizing-segment-trees.html sharmaeklavya2.github.io — Generalizing Segment Trees]
	Демонстрация:		Демонстрация:
	* [http://visualgo.net/segmenttree.html VisuAlgo — Segment Tree]		* [http://visualgo.net/segmenttree.html VisuAlgo — Segment Tree]
	Код:		Код:
	* [http://github.com/indy256/codelibrary/blob/master/~~java~~/~~src~~/~~SegmentTree~~.~~java~~ CodeLibrary — Segment tree]		* [http://www.sites.google.com/site/indy256/algo/segment_tree indy256 — Segment Tree with interval modification]
			* [http://www.sites.google.com/site/indy256/algo/segment_tree_fast indy256 — Segment Tree with interval modification without recursion]
			* [http://github.com/indy256/codelibrary/blob/master/cpp/structures/segment_tree.h CodeLibrary — Segment tree]
	* [http://github.com/ADJA/algos/blob/master/DataStructures/SegmentTree(Assign-Sum).cpp Algos — Segment Tree (Assign-Sum)]		* [http://github.com/ADJA/algos/blob/master/DataStructures/SegmentTree(Assign-Sum).cpp Algos — Segment Tree (Assign-Sum)]
	* [http://github.com/ADJA/algos/blob/master/DataStructures/ImplicitSegmentTree.cpp Algos — Implicit segment tree]		* [http://github.com/ADJA/algos/blob/master/DataStructures/ImplicitSegmentTree.cpp Algos — Implicit segment tree]

Ctrlalt: /* Ссылки */

2016-06-15T20:53:00Z

Ссылки

← Предыдущая версия		Версия от 20:53, 15 июня 2016
Строка 179:		Строка 179:
	* [http://brestprog.neocities.org/lections/segmenttree.html brestprog.neocities.org — Дерево отрезков]		* [http://brestprog.neocities.org/lections/segmenttree.html brestprog.neocities.org — Дерево отрезков]
	* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/mipt-2014-burunduk1-ds.pdf Копелиович С. Лекция про структуры данных Зимней школы МФТИ]		* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/mipt-2014-burunduk1-ds.pdf Копелиович С. Лекция про структуры данных Зимней школы МФТИ]
			* [http://i.cs.hku.hk/~provinci/training2015/notes3.pdf i.cs.hku.hk — Segment Trees: Applications]
	Демонстрация:		Демонстрация:
	* [http://visualgo.net/segmenttree.html VisuAlgo — Segment Tree]		* [http://visualgo.net/segmenttree.html VisuAlgo — Segment Tree]

Ctrlalt: /* Ссылки */

2016-06-04T21:45:32Z

Ссылки

← Предыдущая версия		Версия от 21:45, 4 июня 2016
Строка 186:		Строка 186:
	* [http://github.com/ADJA/algos/blob/master/DataStructures/ImplicitSegmentTree.cpp Algos — Implicit segment tree]		* [http://github.com/ADJA/algos/blob/master/DataStructures/ImplicitSegmentTree.cpp Algos — Implicit segment tree]
	Задачи:		Задачи:
	* [http://informatics.mccme.ru/~~course~~/~~view.php?id=18~~ informatics.mccme.ru — ~~Курс~~ «~~Структуры данных~~» ~~— часть 5~~]		* [http://informatics.mccme.ru/py-source/source/dir/420 informatics.mccme.ru — Тема «Дерево отрезков, RSQ, RMQ»]
	* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_segtree_tasks_C.pdf ~~Задачи группы~~ C ~~Зимней школы МФТИ~~]		* Задачи Зимней школы МФТИ: [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_segtree_tasks_C.pdf группа C], [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_segtree_tasks_B.pdf группа B], [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_segtree_tasks_A.pdf группа A]
	* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_segtree_tasks_B.pdf ~~Задачи группы~~ B ~~Зимней школы МФТИ~~]
	* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_segtree_tasks_A.pdf ~~Задачи группы~~ A ~~Зимней школы МФТИ~~]
	* [[:Категория:Задачи: Дерево отрезков\|Задачи: Дерево отрезков]]		* [[:Категория:Задачи: Дерево отрезков\|Задачи: Дерево отрезков]]

	[[Category:Структуры данных для задач RSQ/RMQ]]		[[Category:Структуры данных для задач RSQ/RMQ]]

Ctrlalt: /* Ссылки */

2016-06-02T13:56:06Z

Ссылки

← Предыдущая версия		Версия от 13:56, 2 июня 2016
Строка 178:		Строка 178:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.BE.D1.82.D1.80.D0.B5.D0.B7.D0.BA.D0.BE.D0.B2 neerc.ifmo.ru/wiki — Дерево отрезков]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.BE.D1.82.D1.80.D0.B5.D0.B7.D0.BA.D0.BE.D0.B2 neerc.ifmo.ru/wiki — Дерево отрезков]
	* [http://brestprog.neocities.org/lections/segmenttree.html brestprog.neocities.org — Дерево отрезков]		* [http://brestprog.neocities.org/lections/segmenttree.html brestprog.neocities.org — Дерево отрезков]
			* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/mipt-2014-burunduk1-ds.pdf Копелиович С. Лекция про структуры данных Зимней школы МФТИ]
	Демонстрация:		Демонстрация:
	* [http://visualgo.net/segmenttree.html VisuAlgo — Segment Tree]		* [http://visualgo.net/segmenttree.html VisuAlgo — Segment Tree]
Строка 186:		Строка 187:
	Задачи:		Задачи:
	* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 5]		* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 5]
	* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_segtree_tasks_C.pdf Задачи Зимней школы МФТИ]		* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_segtree_tasks_C.pdf Задачи группы C Зимней школы МФТИ]
			* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_segtree_tasks_B.pdf Задачи группы B Зимней школы МФТИ]
			* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_segtree_tasks_A.pdf Задачи группы A Зимней школы МФТИ]
	* [[:Категория:Задачи: Дерево отрезков\|Задачи: Дерево отрезков]]		* [[:Категория:Задачи: Дерево отрезков\|Задачи: Дерево отрезков]]

	[[Category:Структуры данных для задач RSQ/RMQ]]		[[Category:Структуры данных для задач RSQ/RMQ]]