Прежде всего, если вы новичок в работе с деревом сегментов, не ждите от этой статьи подробных объяснений того, как работает дерево сегментов. Хотя я добавил некоторые рисунки и полные коды, которые определенно дадут вам почти полное представление об основных проблемах дерева сегментов и его использовании. В любом случае, основная цель этой статьи - сохранить для меня ссылку, чтобы я мог просмотреть ее, когда я не смогу ее вспомнить.
Содержание:
- Запрос суммы диапазона (RSQ)
- Запрос мин. / Макс. Диапазона (RMQ)
- Отсчет нулевого диапазона
- K’th Zero Index
- Дерево сортировки слиянием
- 2D-сегментное дерево
- Постоянное дерево сегментов
1. Запрос суммы диапазона (RSQ):
Запрос суммы диапазона, также известный как RSQ, является самой простой проблемой для изучения дерева сегментов.
Given an array A of N integers. There will be 3 types of operations: UpdateSingle, UpdateRange and Query. 1. UpdateSingle operation consists of 2 integers: i and v. Set value v to index i. 2. UpdateRange operation consists of 3 integers: l, r and v. Set value v to all integers from index l to index r of the array. 3. Query operation consists of 2 integers: l and r. Print the sum of integers from index l to r of the array. Example: A = [2, 5, 1, 3] Query(1, 2) -- Output = 5 + 1 = 6 UpdateRange(2, 3, 10) -- A = [2, 5, 10, 10] Query(0, 3) -- Output = 2 + 5 + 10 + 10 = 27 UpdateSingle(0, 100) -- A = [100, 5, 10, 10] Query(0, 3) -- Output = 100 + 5 + 10 + 10 = 125 Note: Index is zero based
Операции с деревом сегментов приведены ниже:
build(int p, int l, int r) This method will build segment tree from array A which is given initially. If there is no initial array or all values of the array is 0 then no need to execute this method to build segment tree. updateSingle(int p, int l, int r, int i, int val) This method will update value at index i by the given value val and the segment tree as well to make it consistent. updateRange(int p, int l, int r, int i, int j, int val) This method will update some range [i, j] of the array by the given value val and update the segment tree as well to make it consistent. query(int p, int l, int r, int i, int j) This method will return the desired result which we are interested to know between the index i and j.
Как выглядит дерево сегментов
Реализации:
Мы собираемся удерживать сегмент в массиве. Таким образом, если родитель находится в индексе p, тогда левый дочерний элемент будет помещен в индекс 2 * p и 2 * p + 1 для правого дочернего элемента.
#define MAX 1000000
inline int left(int p) { return p << 1; }
inline int right(int p) { return (p << 1) + 1; }
struct Node {
ULL sum = 0;
void setSum(ULL val) {
sum = val;
}
void combine(Node &a, Node &b) {
sum = a.sum + b.sum;
}
};
int N;
int A[MAX];
Node st[3 * MAX];
// Complexity: O(2N-1) = O(N)
void build(int p, int l, int r) {
if (l == r) {
st[p].setSum(A[l]);
return;
}
int mid = (l + r) >> 1;
build(left(p), l, mid);
build(right(p), mid+1, r);
st[p].combine(st[left(p)], st[right(p)]);
}
// Complexity: O(lg N)
void updateSingle(int p, int l, int r, int i, int val) {
if (l == r) {
st[p].setSum(val);
return;
}
int mid = (l + r) >> 1;
if (i <= mid) updateSingle(left(p), l, mid, i, val);
else updateSingle(right(p), mid+1, r, i, val);
st[p].combine(st[left(p)], st[right(p)]);
}
// Complexity: O(N)
void updateRange(int p, int l, int r, int i, int j, int val) {
// Sorry. You have to learn this in next section of this article where lazy propagation is discussed. Anyway you can implement this method without lazy propagation but complexity will be O(abs(i-j)) which is worthless.
}
// Complexity: O(lg N)
Node query(int p, int l, int r, int i, int j) {
if (i == l && j == r) return st[p];
int mid = (l + r) >> 1;
if (j <= mid) return query(left(p), l, mid, i, j);
if (i > mid) return query(right(p), mid + 1, r, i, j);
Node ret;
Node lNode = query(left(p), l, mid, i, mid);
Node rNode = query(right(p), mid+1, r, mid+1, j);
ret.combine(lNode, rNode);
return ret;
}
Ленивое распространение:
С ленивым распространением мы можем запустить метод updateRange () быстрее со сложностью O (lg N). Как? Что ж, при обновлении диапазона нет необходимости опускаться до конечных узлов, когда это возможно. Например, обновите диапазон от индекса 0 до 2 со значением 10:
Обратите внимание, что в узле p = 2 мы сохранили lazy = 10, которое будет распространено на его дочерний элемент при необходимости в следующей операции updateRange () / query (). На диаграмме выше обновляются только узлы красного цвета. Не все листовые узлы в диапазоне 0 ~ 2 обновляются, поэтому сложность составляет O (ln N).
Реализации:
#define MAX 1000000
inline int left(int p) { return p << 1; }
inline int right(int p) { return (p << 1) + 1; }
struct Node {
ULL sum = 0;
int lazy = INT_MIN;
void resetNode() {
sum = 0;
lazy = INT_MIN;
}
void setSum(ULL val) {
sum = val;
}
void combine(Node &a, Node &b) {
sum = a.sum + b.sum;
}
};
void build(int p, int l, int r) {
if (l == r) {
st[p].setSum(A[l]);
return;
}
int mid = (l + r) >> 1;
build(left(p), l, mid);
build(right(p), mid+1, r);
st[p].combine(st[left(p)], st[right(p)]);
}
void pushUp(int p) {
st[p].combine(st[left(p)], st[right(p)]);
}
void pushDown(int p, int l, int r) {
if (st[p].lazy == INT_MIN) return;
int mid = (l + r) >> 1;
st[left(p)].setSum((ULL)(mid-l+1) * st[p].lazy);
st[right(p)].setSum((ULL)(r-mid+1) * st[p].lazy);
st[p].lazy = st[p].lazy = st[p].lazy;
st[p].lazy = INT_MIN;
}
void updateRangeLazy(int p, int l, int r, int i, int j, int val) {
if (i == l && j == r) {
st[p].setSum((ULL)(r - l + 1) * val);
if (l != r) st[p].lazy = val;
return;
}
pushDown(p, l, r);
int mid = (l + r) >> 1;
if (j <= mid) updateRangeLazy(left(p), l, mid, i, j, val);
else if (i > mid) updateRangeLazy(right(p), mid + 1, r, i, j, val);
else {
updateRangeLazy(left(p), l, mid, i, mid, val);
updateRangeLazy(right(p), mid + 1, r, mid + 1, j, val);
}
pushUp(p);
}
Node queryLazy(int p, int l, int r, int i, int j) {
if (i == l && j == r) return st[p];
pushDown(p, l, r);
int mid = (l + r) >> 1;
if (j <= mid) return queryLazy(left(p), l, mid, i, j);
if (i > mid) return queryLazy(right(p), mid + 1, r, i, j);
Node ret;
Node ln = queryLazy(left(p), l, mid, i, mid);
Node rn = queryLazy(right(p), mid + 1, r, mid+1, j);
ret.combine(ln, rn);
return ret;
}
Вы можете найти полный код здесь. Ссылка на Github.
Вариант RSQ:
Мы можем изменить определение updateRange (), как показано ниже:
UpdateRange operation consists of 3 integers: l, r and v. Add (It was set previously) value v to all integers from index l to index r of the array.
В этом случае требуются следующие изменения:
// Change in Node initial values
struct Node {
ULL sum = 0;
int lazy = 0; // Changed line
void resetNode() {
sum = 0;
lazy = 0; // Changed line
}
void setSum(ULL val) {
sum = val;
}
void combine(Node &a, Node &b) {
sum = a.sum + b.sum;
}
};
// Change in pushDown() method
void pushDown(int p, int l, int r) {
if (st[p].lazy == INT_MIN) return;
int mid = (l + r) >> 1;
st[left(p)].setSum((ULL)(mid-l+1) * st[p].lazy);
st[right(p)].setSum((ULL)(r-mid+1) * st[p].lazy);
st[p].lazy += st[p].lazy; // Changed line
st[p].lazy += st[p].lazy; // Change line
st[p].lazy = INT_MIN;
}
void updateRangeLazy(int p, int l, int r, int i, int j, int val) {
if (i == l && j == r) {
st[p].setSum((ULL)(r - l + 1) * val);
if (l != r) st[p].lazy += val;
return;
}
pushDown(p, l, r);
int mid = (l + r) >> 1;
if (j <= mid) updateRangeLazy(left(p), l, mid, i, j, val);
else if (i > mid) updateRangeLazy(right(p), mid + 1, r, i, j, val);
else {
updateRangeLazy(left(p), l, mid, i, mid, val);
updateRangeLazy(right(p), mid + 1, r, mid + 1, j, val);
}
pushUp(p);
}
Практические задачи:
2. Запрос минимального / максимального диапазона (RMQ):
Практически аналогично RSQ, эта постановка задачи требует вместо суммы найти минимальное значение заданного диапазона.
Вы можете найти полный код здесь. Ссылка на Github.
Практические задачи:
- Https://www.spoj.com/problems/GSS1/
- Https://www.spoj.com/problems/GSS3/
- Https://www.spoj.com/problems/RPLN/
- Https://www.spoj.com/problems/HISTOGRA/
3. Отсчет нуля диапазона:
Постановка задачи просит найти количество случаев появления 0 в заданном диапазоне.
Given an array A of N integers. There will be 3 types of operations: UpdateSingle, UpdateRange and Query. 1. UpdateSingle operation consists of 2 integers: i and v. Set value v to index i. 2. UpdateRange operation consists of 3 integers: l, r and v. Set value v to all integers from index l to index r of the array. 3. Query operation consists of 2 integers: l and r. Print the count of zeros from index l to index r of the array. Example: A = [1, 0, 3, 0, 0, 5, 6, 0] Query(0, 3) -- Output = 2 Query(0, 7) -- Output = 4 UpdateRange(0, 2, 1) -- A = [1, 1, 1, 0, 0, 5, 6, 0] Query(0, 7) -- Output = 3
Реализация очень похожа на RSQ. Однако вы можете найти полный код здесь. Ссылка на Github.
RMQ с частотой:
Это похоже на комбинацию RMQ и отсчета нулевого диапазона, но это не совсем так. Здесь нам нужно найти значение RMQ и его частоту в заданном диапазоне [l, r].
Given an array A of N integers. There will be 3 types of operations: UpdateRange and Query. 1. UpdateRange operation consists of 3 integers: l, r and v. Set value v to all integers from index l to index r of the array. 2. Query operation consist of 2 integers: l and r. Print minimum integer and it's frequency from index l to r of the array. Example: A = [1, 0, 3, 0, 0, 5, 6, 0] Query(0, 3) -- Output = (min = 0, freq = 2) Query(0, 7) -- Output = (min = 0, freq = 4) UpdateRange(0, 2, 1) -- A = [1, 1, 1, 0, 0, 5, 6, 0] Query(0, 7) -- Output = (min = 0, freq = 3)
В методе объединения узла требуется небольшое изменение, чтобы сохранить как частоту, так и минимальное значение. Мне не интересно писать код для этого прямо сейчас.
4. K’th Zero Index:
Эта задача почти так же, как Range Zero Count, требует найти индекс k-го нуля в массиве. Также должна поддерживаться операция обновления диапазона.
Given an array A of N integers. There will be 3 types of operations: UpdateSingle, UpdateRange and Query. 1. UpdateSingle operation consists of 2 integers: i and v. Set value v to index i. 2. UpdateRange operation consists of 3 integers: l, r and v. Set value v to all integers from index l to index r of the array. 3. Query operation consists of 1 integer: k. Print the index of k'th zero in the array. Example: A = [1, 0, 3, 0, 0, 5, 6, 0] Query(1) -- Output = 1 Query(2) -- Output = 3 Query(3) -- Output = 4 UpdateRange(0, 2, 1) -- A = [1, 1, 1, 0, 0, 5, 6, 0] Query(0, 7) -- Output = 3
Взгляните на реализацию здесь. Ссылка на GitHub.
Нетривиальные проблемы дерева сегментов:
Прежде чем двигаться дальше, мы можем решить следующие проблемы в дереве сегментов, которые помогут нам укрепить идею и реализацию дерева сегментов:
- Https://www.spoj.com/problems/SEGSQRSS/
- Https://www.spoj.com/problems/MULTQ3/
- Https://www.spoj.com/problems/ANDROUND/
- Https://www.spoj.com/problems/LITE/
- Https://codeforces.com/problemset/problem/339/D
- Https://www.codechef.com/problems/FLIPCOIN
5. Объединить дерево сортировки
Помните технику сортировки слиянием? Используя подход DnC (разделяй и властвуй), мы объединяем каждый отсортированный слева и справа массив с родительским узлом. В конце концов, мы получаем отсортированный массив в корневом узле, который является окончательной сортировкой слияния на выходе.
В дереве сортировки слиянием мы сохраним отсортированный список в каждом узле, чтобы мы могли использовать их для различных приложений. В любом случае, вместо подробного описания, давайте взглянем на Дерево сортировки слиянием:
Приведенное выше дерево сортировки слиянием построено с помощью массива A = [4, 3, 2, 1].
Построение дерева сортировки слиянием
Нет большой разницы с логикой построения обычного дерева сегментов. Каждый узел содержит вектор, в котором будут храниться все отсортированные элементы. Итак, сколько памяти и времени работы необходимо для построения дерева сортировки слиянием?
Сложность пространства. Обратите внимание, что для каждого уровня дерева существует N целых чисел. Общий уровень / высота дерева lgN. Таким образом, общий объем памяти равен O (N * lgN).
Сложность времени. Обратите внимание, что для каждого уровня нам приходилось проходить через массив один раз. Общий уровень / высота дерева lgN. Итак, общее время выполнения O (N * lgN).
Подсчитайте целые числа меньше K в диапазоне:
Давайте обсудим общую проблему, для которой требуется дерево сортировки слиянием.
Given an array of N elements and we have to answer Q queries of the form L R K, To Count the numbers smaller than K in range L to R. Example: A = [5, 4, 1, 3, 0, 10, 6, 2] Query(2, 7, 7) = 5 -- Only 10 is greater than 7 Query(2, 0, 5) = 5 -- [4, 1, 3, 0, 2]
Решение:
queryCountSmallerThanK(int p, int l, int r, int i, int j, int k) Return number of integers smaller then k in the range (i, j) Main Idea: Running regular query on segment tree when (i == l && j == r) do a binary search to get count number of integers less than k for that node. Answer will be sum of sub queries. Complexity: Regular segment tree complexity is O(lgN). In this case for each level/height we are running a binary search. So complexity is O(lgN * lgN). Doesn't it cool !!!
Вы можете найти код здесь - Github Link.
6. 2D-сегментное дерево:
Давайте посмотрим на проблему RSQ для 2D-сетки:
Given an 2D array A of N rows and M columns. There will be 3 types of operations: UpdateSinge and Query.
1. UpdateSingle operation consists of 3 integers: i, j and v.
Set value v to index [i, j].
2. Query operation consists of 4 integers: i, j, k, and l.
Print the sum of all integers from point [i, j] to [k, l]
Example:
A = [ 1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6 ]
Query(1, 1, 2, 2) -- Output = 6 + 7 + 0 + 1 = 14
UpdateSingle(2, 1, 10) -- A[2][1] = 10
Query(1, 1, 2, 2) -- Output = 6 + 7 + 10 + 1 = 24
Note: I didn't discuss UpdateRange operation of 2D segment tree because until now I don't know how to do that. Give me a good reference. TIA.
Построение двухмерного дерева сегментов.
Сначала немного непонятно думать о 2D-дереве сегментов и визуализации 2D-дерева сегментов. Основная идея состоит в том, чтобы построить деревья сегментов для каждой строки и другого дерева сегментов в порядке столбцов, используя те деревья сегментов, которые будут хранить суммы по вертикали. Давайте попробуем визуализировать двумерное дерево сегментов:
| 0 1 2 3 ----------- 0 | 1 2 3 4 1 | 5 6 7 8 2 | 9 0 1 2 3 | 3 4 5 6 Above matrix has N = 4 rows and M = 4 columns.
Здесь для каждой строки создаются деревья сегментов:
Теперь мы должны рассматривать каждый массив как элемент другого массива, потому что мы должны построить окончательное дерево сегментов, используя эти деревья сегментов. Это будет выглядеть так:
Хорошо!. 2D-дерево сегментов построено успешно.
Сложность сборки: O ((2N-1) * (2M-1)) = O (NM)
Обновить дерево двухмерных сегментов.
Обновление почти похоже на сборку, за исключением того, что оно распространяется на узлы, которые необходимо обновить. Таким образом, сложность запроса на обновление приведена ниже:
Сложность обновления: O (lg N * lg M)
Дерево двухмерных сегментов запроса.
Пришло время выполнить запрос. Попробуем визуализировать запрос - Запрос (1, 1, 2, 3):
| 0 1 2 3 ----------- 0 | 1 2 3 4 1 | 5 6 7 8 2 | 9 0 1 2 3 | 3 4 5 6 We are going to find sum of the highlighted segment in the above matrix. Sum of the segment is the sum for following sub query: Query(1, 1, 2, 3) = Sum of Row range (1, 2) to Column Range (1, 3) = Query(1, 1, 1, 3) + Query(2, 1, 2, 3) = (st[1][5] + st[1][3]) + (st[2][5] + st[2][3]) = 6 + 15 + 3 = 24
Давайте попробуем другой запрос - Запрос (0, 0, 1, 3)
| 0 1 2 3 ----------- 0 | 1 2 3 4 1 | 5 6 7 8 2 | 9 0 1 2 3 | 3 4 5 6 Query(0, 0, 1, 3) = Sum of Row range (0, 1) to Column Range (0, 3) = st[2][1] = 36
Сложность запроса: O (lg N * lg M)
Реализация:
Реализация довольно долгая. Так что лучше взгляните на Github Link.
Практические задачи:
7. Постоянное дерево сегментов
В постоянном дереве сегментов сохраняются все версии дерева сегментов после каждой модификации, поэтому, если в дереве сегментов есть какие-либо изменения, мы все равно можем получить доступ к предыдущим версиям дерева сегментов и запросить это старое дерево, как обычный запрос. Пример приведен ниже:
Initial Array = { 8, 7, 3, 9, 5, 1, 10 }
Modification 1: Update value at index 2 with value 15.
Modification 2: Update value at index 6 with value 20.
Modification 3: Update value at index 1 with value 100.
Now find sum of range from index 1 to 4 after 1st modification. In these cases persistent segment tree is used.
Практические задачи:
