Как реализовать сегментные деревья с ленивым распространением?
Я искал в Интернете о внедрении деревьев сегментов, но ничего не нашел, когда дело дошло до ленивого распространения. Были некоторые предыдущие вопросы о переполнении стека, но они были сосредоточены на решении некоторых конкретных проблем SPOJ. Хотя я думаю, что это лучшее объяснение деревьев сегментов с псевдокодом, но мне нужно реализовать его с ленивым распространением. Я нашел следующие ссылки:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
В дополнение к вышеупомянутой ссылке, некоторые блоги также были там, но все они давали ссылку на ту же ветку.
пример
Примером применения этой структуры данных было бы что-то вроде, скажем, мне дали диапазон чисел от 1 до n. Теперь я выполняю некоторые операции, такие как добавление некоторого постоянного числа к определенному диапазону или вычитание некоторого постоянного числа из определенного диапазона. После выполнения операций я должен указать минимальное и максимальное количество в данном номере.
Очевидное решение состоит в том, чтобы выполнить сложение или вычитание для каждого числа в данном диапазоне один за другим. Но это не может быть осуществимо в ситуации, когда ни одна из выполняемых операций не является большой.
Лучшим подходом было бы использовать деревья сегментов с техникой ленивого распространения. В нем говорится, что вместо выполнения операции обновления для каждого номера в отдельности, просто следите за всеми операциями, пока все операции не будут выполнены. Затем, наконец, выполните операцию обновления, чтобы получить минимальное и максимальное число в диапазоне.
Пример с реальными данными
Предположим, я дал диапазон [1,10], что означает числа 1,2,3,4,5,6,7,8,9,10. Теперь предположим, что я выполняю операцию, которая уменьшает числа в диапазоне [3,6] на 4, так что теперь числа будут выглядеть как 1,2,-1,0,1,2,7,8,9,10. Теперь я выполняю еще одну операцию, которая увеличивает числа в диапазоне [5,9] на 1, поэтому теперь число будет выглядеть как 1,2,-1,0,2,3,8,9,10,10.
Теперь, если я попрошу вас указать максимальное и минимальное число, ответ будет таким:
Maximum = 10
Minimum = -1
Это простой пример. Фактическая проблема может содержать тысячи таких операций сложения / вычитания. Надеюсь, теперь это понятно.
Это то, что я понял до сих пор, но я думаю, что в Интернете нет единой ссылки, которая бы лучше объясняла концепцию и реализацию.
Может ли кто-нибудь дать хорошее объяснение, включая псевдокод для ленивого распространения в деревьях сегментов?
Благодарю.
5 ответов
Ленивое распространение почти всегда включает какой-то часовой механизм. Вы должны убедиться, что текущий узел не нужно распространять, и эта проверка должна быть простой и быстрой. Итак, есть две возможности:
- Пожертвуйте немного памяти, чтобы сохранить поле в вашем узле, которое можно очень легко проверить
- Пожертвуйте немного времени выполнения, чтобы проверить, был ли распространен узел и должны ли быть созданы его дочерние узлы.
Я придерживался первого. Очень просто проверить, должны ли узлы в сегментированном дереве иметь дочерние узлы (node->lower_value != node->upper_value), но вам также необходимо проверить, созданы ли эти дочерние узлы (node->left_child, node->right_child), поэтому я ввел флаг распространения node->propagated:
typedef struct lazy_segment_node{
int lower_value;
int upper_value;
struct lazy_segment_node * left_child;
struct lazy_segment_node * right_child;
unsigned char propagated;
} lazy_segment_node;
инициализация
Для инициализации узла мы вызываем initialize с указателем на указатель узла (или NULL) и желаемый upper_value/lower_value:
lazy_segment_node * initialize(
lazy_segment_node ** mem,
int lower_value,
int upper_value
){
lazy_segment_node * tmp = NULL;
if(mem != NULL)
tmp = *mem;
if(tmp == NULL)
tmp = malloc(sizeof(lazy_segment_node));
if(tmp == NULL)
return NULL;
tmp->lower_value = lower_value;
tmp->upper_value = upper_value;
tmp->propagated = 0;
tmp->left_child = NULL;
tmp->right_child = NULL;
if(mem != NULL)
*mem = tmp;
return tmp;
}
Доступ
Пока ничего особенного сделано не было. Это похоже на любой другой метод создания общего узла. Однако, чтобы создать фактические дочерние узлы и установить флаги распространения, мы можем использовать функцию, которая будет возвращать указатель на тот же узел, но распространять его при необходимости:
lazy_segment_node * accessErr(lazy_segment_node* node, int * error){
if(node == NULL){
if(error != NULL)
*error = 1;
return NULL;
}
/* if the node has been propagated already return it */
if(node->propagated)
return node;
/* the node doesn't need child nodes, set flag and return */
if(node->upper_value == node->lower_value){
node->propagated = 1;
return node;
}
/* skipping left and right child creation, see code below*/
return node;
}
Как видите, размноженный узел выйдет из функции почти сразу. Нераспространенный узел вместо этого сначала проверит, должен ли он на самом деле содержать дочерние узлы, а затем создаст их при необходимости.
Это на самом деле ленивая оценка. Вы не создаете дочерние узлы до тех пор, пока они не понадобятся. Обратите внимание, что accessErr также предоставляет дополнительный интерфейс ошибок. Если вам это не нужно, используйте access вместо:
lazy_segment_node * access(lazy_segment_node* node){
return accessErr(node,NULL);
}
Свободно
Чтобы освободить эти элементы, вы можете использовать общий алгоритм освобождения узла:
void free_lazy_segment_tree(lazy_segment_node * root){
if(root == NULL)
return;
free_lazy_segment_tree(root->left_child);
free_lazy_segment_tree(root->right_child);
free(root);
}
Полный пример
В следующем примере будут использоваться функции, описанные выше, для создания лениво оцененного дерева сегментов на основе интервала [1,10]. Вы можете увидеть это после первой инициализации test не имеет дочерних узлов. Используя access вы фактически генерируете эти дочерние узлы и можете получить их значения (если эти дочерние узлы существуют по логике сегментированного дерева):
Код
#include <stdlib.h>
#include <stdio.h>
typedef struct lazy_segment_node{
int lower_value;
int upper_value;
unsigned char propagated;
struct lazy_segment_node * left_child;
struct lazy_segment_node * right_child;
} lazy_segment_node;
lazy_segment_node * initialize(lazy_segment_node ** mem, int lower_value, int upper_value){
lazy_segment_node * tmp = NULL;
if(mem != NULL)
tmp = *mem;
if(tmp == NULL)
tmp = malloc(sizeof(lazy_segment_node));
if(tmp == NULL)
return NULL;
tmp->lower_value = lower_value;
tmp->upper_value = upper_value;
tmp->propagated = 0;
tmp->left_child = NULL;
tmp->right_child = NULL;
if(mem != NULL)
*mem = tmp;
return tmp;
}
lazy_segment_node * accessErr(lazy_segment_node* node, int * error){
if(node == NULL){
if(error != NULL)
*error = 1;
return NULL;
}
if(node->propagated)
return node;
if(node->upper_value == node->lower_value){
node->propagated = 1;
return node;
}
node->left_child = initialize(NULL,node->lower_value,(node->lower_value + node->upper_value)/2);
if(node->left_child == NULL){
if(error != NULL)
*error = 2;
return NULL;
}
node->right_child = initialize(NULL,(node->lower_value + node->upper_value)/2 + 1,node->upper_value);
if(node->right_child == NULL){
free(node->left_child);
if(error != NULL)
*error = 3;
return NULL;
}
node->propagated = 1;
return node;
}
lazy_segment_node * access(lazy_segment_node* node){
return accessErr(node,NULL);
}
void free_lazy_segment_tree(lazy_segment_node * root){
if(root == NULL)
return;
free_lazy_segment_tree(root->left_child);
free_lazy_segment_tree(root->right_child);
free(root);
}
int main(){
lazy_segment_node * test = NULL;
initialize(&test,1,10);
printf("Lazy evaluation test\n");
printf("test->lower_value: %i\n",test->lower_value);
printf("test->upper_value: %i\n",test->upper_value);
printf("\nNode not propagated\n");
printf("test->left_child: %p\n",test->left_child);
printf("test->right_child: %p\n",test->right_child);
printf("\nNode propagated with access:\n");
printf("access(test)->left_child: %p\n",access(test)->left_child);
printf("access(test)->right_child: %p\n",access(test)->right_child);
printf("\nNode propagated with access, but subchilds are not:\n");
printf("access(test)->left_child->left_child: %p\n",access(test)->left_child->left_child);
printf("access(test)->left_child->right_child: %p\n",access(test)->left_child->right_child);
printf("\nCan use access on subchilds:\n");
printf("access(test->left_child)->left_child: %p\n",access(test->left_child)->left_child);
printf("access(test->left_child)->right_child: %p\n",access(test->left_child)->right_child);
printf("\nIt's possible to chain:\n");
printf("access(access(access(test)->right_child)->right_child)->lower_value: %i\n",access(access(access(test)->right_child)->right_child)->lower_value);
printf("access(access(access(test)->right_child)->right_child)->upper_value: %i\n",access(access(access(test)->right_child)->right_child)->upper_value);
free_lazy_segment_tree(test);
return 0;
}
Результат (ideone)
Ленивый оценочный тест test->lower_value: 1 test->upper_value: 10 Узел не размножается test->left_child: (ноль) test->right_child: (ноль) Узел распространяется с доступом: доступ (тест)->left_child: 0x948e020 доступ (тест)->right_child: 0x948e038 Узел распространяется с доступом, но подчиненные не являются: доступ (тест)->left_child->left_child: (ноль) доступ (тест)->left_child->right_child: (ноль) Можно использовать доступ к дочерним элементам: доступ (test->left_child)->left_child: 0x948e050 доступ (test->left_child)->right_child: 0x948e068 Возможно связать доступ (доступ (доступ (тест)->right_child)->right_child)->lower_value: 9 доступ (доступ (доступ (тест)->right_child)->right_child)->upper_value: 10
Если кто-то ищет дальнейший простой код ленивого распространения без использования структур:
(код не требует пояснений)
/**
* In this code we have a very large array called arr, and very large set of operations
* Operation #1: Increment the elements within range [i, j] with value val
* Operation #2: Get max element within range [i, j]
* Build tree: build_tree(1, 0, N-1)
* Update tree: update_tree(1, 0, N-1, i, j, value)
* Query tree: query_tree(1, 0, N-1, i, j)
*/
#include<iostream>
#include<algorithm>
using namespace std;
#include<string.h>
#include<math.h>
#define N 20
#define MAX (1+(1<<6)) // Why? :D
#define inf 0x7fffffff
int arr[N];
int tree[MAX];
int lazy[MAX];
/**
* Build and init tree
*/
void build_tree(int node, int a, int b) {
if(a > b) return; // Out of range
if(a == b) { // Leaf node
tree[node] = arr[a]; // Init value
return;
}
build_tree(node*2, a, (a+b)/2); // Init left child
build_tree(node*2+1, 1+(a+b)/2, b); // Init right child
tree[node] = max(tree[node*2], tree[node*2+1]); // Init root value
}
/**
* Increment elements within range [i, j] with value value
*/
void update_tree(int node, int a, int b, int i, int j, int value) {
if(lazy[node] != 0) { // This node needs to be updated
tree[node] += lazy[node]; // Update it
if(a != b) {
lazy[node*2] += lazy[node]; // Mark child as lazy
lazy[node*2+1] += lazy[node]; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(a > b || a > j || b < i) // Current segment is not within range [i, j]
return;
if(a >= i && b <= j) { // Segment is fully within range
tree[node] += value;
if(a != b) { // Not leaf node
lazy[node*2] += value;
lazy[node*2+1] += value;
}
return;
}
update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child
update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child
tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value
}
/**
* Query tree to get max element value within range [i, j]
*/
int query_tree(int node, int a, int b, int i, int j) {
if(a > b || a > j || b < i) return -inf; // Out of range
if(lazy[node] != 0) { // This node needs to be updated
tree[node] += lazy[node]; // Update it
if(a != b) {
lazy[node*2] += lazy[node]; // Mark child as lazy
lazy[node*2+1] += lazy[node]; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(a >= i && b <= j) // Current segment is totally within range [i, j]
return tree[node];
int q1 = query_tree(node*2, a, (a+b)/2, i, j); // Query left child
int q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); // Query right child
int res = max(q1, q2); // Return final result
return res;
}
int main() {
for(int i = 0; i < N; i++) arr[i] = 1;
build_tree(1, 0, N-1);
memset(lazy, 0, sizeof lazy);
update_tree(1, 0, N-1, 0, 6, 5); // Increment range [0, 6] by 5
update_tree(1, 0, N-1, 7, 10, 12); // Incremenet range [7, 10] by 12
update_tree(1, 0, N-1, 10, N-1, 100); // Increment range [10, N-1] by 100
cout << query_tree(1, 0, N-1, 0, N-1) << endl; // Get max element in range [0, N-1]
}
Ссылка на эту ссылку для более подробного объяснения Сегмент деревьев и ленивое распространение
Хотя я еще не решил ее успешно, я считаю, что эта проблема намного проще, чем мы думаем. Возможно, вам даже не нужно использовать дерево сегментов / дерево интервалов... На самом деле, я попробовал оба способа реализации Segment TreeОдин использует древовидную структуру, а другой использует массив, оба решения быстро получили TLE. У меня есть ощущение, что это можно сделать с помощью Greedy, но я пока не уверен. В любом случае, если вы хотите увидеть, как все делается с помощью дерева сегментов, не стесняйтесь изучать мое решение. Обратите внимание, что max_tree[1] а также min_tree[1] соответствуют max/min,
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <utility>
#include <stack>
#include <deque>
#include <queue>
#include <fstream>
#include <functional>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#ifdef _WIN32 || _WIN64
#define getc_unlocked _fgetc_nolock
#endif
using namespace std;
const int MAX_RANGE = 1000000;
const int NIL = -(1 << 29);
int data[MAX_RANGE] = {0};
int min_tree[3 * MAX_RANGE + 1];
int max_tree[3 * MAX_RANGE + 1];
int added_to_interval[3 * MAX_RANGE + 1];
struct node {
int max_value;
int min_value;
int added;
node *left;
node *right;
};
node* build_tree(int l, int r, int values[]) {
node *root = new node;
root->added = 0;
if (l > r) {
return NULL;
}
else if (l == r) {
root->max_value = l + 1; // or values[l]
root->min_value = l + 1; // or values[l]
root->added = 0;
root->left = NULL;
root->right = NULL;
return root;
}
else {
root->left = build_tree(l, (l + r) / 2, values);
root->right = build_tree((l + r) / 2 + 1, r, values);
root->max_value = max(root->left->max_value, root->right->max_value);
root->min_value = min(root->left->min_value, root->right->min_value);
root->added = 0;
return root;
}
}
node* build_tree(int l, int r) {
node *root = new node;
root->added = 0;
if (l > r) {
return NULL;
}
else if (l == r) {
root->max_value = l + 1; // or values[l]
root->min_value = l + 1; // or values[l]
root->added = 0;
root->left = NULL;
root->right = NULL;
return root;
}
else {
root->left = build_tree(l, (l + r) / 2);
root->right = build_tree((l + r) / 2 + 1, r);
root->max_value = max(root->left->max_value, root->right->max_value);
root->min_value = min(root->left->min_value, root->right->min_value);
root->added = 0;
return root;
}
}
void update_tree(node* root, int begin, int end, int i, int j, int amount) {
// out of range
if (begin > end || begin > j || end < i) {
return;
}
// in update range (i, j)
else if (i <= begin && end <= j) {
root->max_value += amount;
root->min_value += amount;
root->added += amount;
}
else {
if (root->left == NULL && root->right == NULL) {
root->max_value = root->max_value + root->added;
root->min_value = root->min_value + root->added;
}
else if (root->right != NULL && root->left == NULL) {
update_tree(root->right, (begin + end) / 2 + 1, end, i, j, amount);
root->max_value = root->right->max_value + root->added;
root->min_value = root->right->min_value + root->added;
}
else if (root->left != NULL && root->right == NULL) {
update_tree(root->left, begin, (begin + end) / 2, i, j, amount);
root->max_value = root->left->max_value + root->added;
root->min_value = root->left->min_value + root->added;
}
else {
update_tree(root->right, (begin + end) / 2 + 1, end, i, j, amount);
update_tree(root->left, begin, (begin + end) / 2, i, j, amount);
root->max_value = max(root->left->max_value, root->right->max_value) + root->added;
root->min_value = min(root->left->min_value, root->right->min_value) + root->added;
}
}
}
void print_tree(node* root) {
if (root != NULL) {
print_tree(root->left);
cout << "\t(max, min): " << root->max_value << ", " << root->min_value << endl;
print_tree(root->right);
}
}
void clean_up(node*& root) {
if (root != NULL) {
clean_up(root->left);
clean_up(root->right);
delete root;
root = NULL;
}
}
void update_bruteforce(int x, int y, int z, int &smallest, int &largest, int data[], int n) {
for (int i = x; i <= y; ++i) {
data[i] += z;
}
// update min/max
smallest = data[0];
largest = data[0];
for (int i = 0; i < n; ++i) {
if (data[i] < smallest) {
smallest = data[i];
}
if (data[i] > largest) {
largest = data[i];
}
}
}
void build_tree_as_array(int position, int left, int right) {
if (left > right) {
return;
}
else if (left == right) {
max_tree[position] = left + 1;
min_tree[position] = left + 1;
added_to_interval[position] = 0;
return;
}
else {
build_tree_as_array(position * 2, left, (left + right) / 2);
build_tree_as_array(position * 2 + 1, (left + right) / 2 + 1, right);
max_tree[position] = max(max_tree[position * 2], max_tree[position * 2 + 1]);
min_tree[position] = min(min_tree[position * 2], min_tree[position * 2 + 1]);
}
}
void update_tree_as_array(int position, int b, int e, int i, int j, int value) {
if (b > e || b > j || e < i) {
return;
}
else if (i <= b && e <= j) {
max_tree[position] += value;
min_tree[position] += value;
added_to_interval[position] += value;
return;
}
else {
int left_branch = 2 * position;
int right_branch = 2 * position + 1;
// make sure the array is ok
if (left_branch >= 2 * MAX_RANGE + 1 || right_branch >= 2 * MAX_RANGE + 1) {
max_tree[position] = max_tree[position] + added_to_interval[position];
min_tree[position] = min_tree[position] + added_to_interval[position];
return;
}
else if (max_tree[left_branch] == NIL && max_tree[right_branch] == NIL) {
max_tree[position] = max_tree[position] + added_to_interval[position];
min_tree[position] = min_tree[position] + added_to_interval[position];
return;
}
else if (max_tree[left_branch] != NIL && max_tree[right_branch] == NIL) {
update_tree_as_array(left_branch, b , (b + e) / 2 , i, j, value);
max_tree[position] = max_tree[left_branch] + added_to_interval[position];
min_tree[position] = min_tree[left_branch] + added_to_interval[position];
}
else if (max_tree[right_branch] != NIL && max_tree[left_branch] == NIL) {
update_tree_as_array(right_branch, (b + e) / 2 + 1 , e , i, j, value);
max_tree[position] = max_tree[right_branch] + added_to_interval[position];
min_tree[position] = min_tree[right_branch] + added_to_interval[position];
}
else {
update_tree_as_array(left_branch, b, (b + e) / 2 , i, j, value);
update_tree_as_array(right_branch, (b + e) / 2 + 1 , e , i, j, value);
max_tree[position] = max(max_tree[position * 2], max_tree[position * 2 + 1]) + added_to_interval[position];
min_tree[position] = min(min_tree[position * 2], min_tree[position * 2 + 1]) + added_to_interval[position];
}
}
}
void show_data(int data[], int n) {
cout << "[current data]\n";
for (int i = 0; i < n; ++i) {
cout << data[i] << ", ";
}
cout << endl;
}
inline void input(int* n) {
char c = 0;
while (c < 33) {
c = getc_unlocked(stdin);
}
*n = 0;
while (c > 33) {
*n = (*n * 10) + c - '0';
c = getc_unlocked(stdin);
}
}
void handle_special_case(int m) {
int type;
int x;
int y;
int added_amount;
for (int i = 0; i < m; ++i) {
input(&type);
input(&x);
input(&y);
input(&added_amount);
}
printf("0\n");
}
void find_largest_range_use_tree() {
int n;
int m;
int type;
int x;
int y;
int added_amount;
input(&n);
input(&m);
if (n == 1) {
handle_special_case(m);
return;
}
node *root = build_tree(0, n - 1);
for (int i = 0; i < m; ++i) {
input(&type);
input(&x);
input(&y);
input(&added_amount);
if (type == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_tree(root, 0, n - 1, x - 1, y - 1, added_amount);
}
printf("%d\n", root->max_value - root->min_value);
}
void find_largest_range_use_array() {
int n;
int m;
int type;
int x;
int y;
int added_amount;
input(&n);
input(&m);
if (n == 1) {
handle_special_case(m);
return;
}
memset(min_tree, NIL, 3 * sizeof(int) * n + 1);
memset(max_tree, NIL, 3 * sizeof(int) * n + 1);
memset(added_to_interval, 0, 3 * sizeof(int) * n + 1);
build_tree_as_array(1, 0, n - 1);
for (int i = 0; i < m; ++i) {
input(&type);
input(&x);
input(&y);
input(&added_amount);
if (type == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_tree_as_array(1, 0, n - 1, x - 1, y - 1, added_amount);
}
printf("%d\n", max_tree[1] - min_tree[1]);
}
void update_slow(int x, int y, int value) {
for (int i = x - 1; i < y; ++i) {
data[i] += value;
}
}
void find_largest_range_use_common_sense() {
int n;
int m;
int type;
int x;
int y;
int added_amount;
input(&n);
input(&m);
if (n == 1) {
handle_special_case(m);
return;
}
memset(data, 0, sizeof(int) * n);
for (int i = 0; i < m; ++i) {
input(&type);
input(&x);
input(&y);
input(&added_amount);
if (type == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_slow(x, y, added_amount);
}
// update min/max
int smallest = data[0] + 1;
int largest = data[0] + 1;
for (int i = 1; i < n; ++i) {
if (data[i] + i + 1 < smallest) {
smallest = data[i] + i + 1;
}
if (data[i] + i + 1 > largest) {
largest = data[i] + i + 1;
}
}
printf("%d\n", largest - smallest);
}
void inout_range_of_data() {
int test_cases;
input(&test_cases);
while (test_cases--) {
find_largest_range_use_common_sense();
}
}
namespace unit_test {
void test_build_tree() {
for (int i = 0; i < MAX_RANGE; ++i) {
data[i] = i + 1;
}
node *root = build_tree(0, MAX_RANGE - 1, data);
print_tree(root);
}
void test_against_brute_force() {
// arrange
int number_of_operations = 100;
for (int i = 0; i < MAX_RANGE; ++i) {
data[i] = i + 1;
}
node *root = build_tree(0, MAX_RANGE - 1, data);
// print_tree(root);
// act
int operation;
int x;
int y;
int added_amount;
int smallest = 1;
int largest = MAX_RANGE;
// assert
while (number_of_operations--) {
operation = rand() % 2;
x = 1 + rand() % MAX_RANGE;
y = x + (rand() % (MAX_RANGE - x + 1));
added_amount = 1 + rand() % MAX_RANGE;
// cin >> operation >> x >> y >> added_amount;
if (operation == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_bruteforce(x - 1, y - 1, added_amount, smallest, largest, data, MAX_RANGE);
update_tree(root, 0, MAX_RANGE - 1, x - 1, y - 1, added_amount);
assert(largest == root->max_value);
assert(smallest == root->min_value);
for (int i = 0; i < MAX_RANGE; ++i) {
cout << data[i] << ", ";
}
cout << endl << endl;
cout << "correct:\n";
cout << "\t largest = " << largest << endl;
cout << "\t smallest = " << smallest << endl;
cout << "testing:\n";
cout << "\t largest = " << root->max_value << endl;
cout << "\t smallest = " << root->min_value << endl;
cout << "testing:\n";
cout << "\n------------------------------------------------------------\n";
cout << "final result: " << largest - smallest << endl;
cin.get();
}
clean_up(root);
}
void test_automation() {
// arrange
int test_cases;
int number_of_operations = 100;
int n;
test_cases = 10000;
for (int i = 0; i < test_cases; ++i) {
n = i + 1;
int operation;
int x;
int y;
int added_amount;
int smallest = 1;
int largest = n;
// initialize data for brute-force
for (int i = 0; i < n; ++i) {
data[i] = i + 1;
}
// build tree
node *root = build_tree(0, n - 1, data);
for (int i = 0; i < number_of_operations; ++i) {
operation = rand() % 2;
x = 1 + rand() % n;
y = x + (rand() % (n - x + 1));
added_amount = 1 + rand() % n;
if (operation == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_bruteforce(x - 1, y - 1, added_amount, smallest, largest, data, n);
update_tree(root, 0, n - 1, x - 1, y - 1, added_amount);
assert(largest == root->max_value);
assert(smallest == root->min_value);
cout << endl << endl;
cout << "For n = " << n << endl;
cout << ", where data is : \n";
for (int i = 0; i < n; ++i) {
cout << data[i] << ", ";
}
cout << endl;
cout << " and query is " << x - 1 << ", " << y - 1 << ", " << added_amount << endl;
cout << "correct:\n";
cout << "\t largest = " << largest << endl;
cout << "\t smallest = " << smallest << endl;
cout << "testing:\n";
cout << "\t largest = " << root->max_value << endl;
cout << "\t smallest = " << root->min_value << endl;
cout << "\n------------------------------------------------------------\n";
cout << "final result: " << largest - smallest << endl;
}
clean_up(root);
}
cout << "DONE............\n";
}
void test_tree_as_array() {
// arrange
int test_cases;
int number_of_operations = 100;
int n;
test_cases = 1000;
for (int i = 0; i < test_cases; ++i) {
n = MAX_RANGE;
memset(min_tree, NIL, sizeof(min_tree));
memset(max_tree, NIL, sizeof(max_tree));
memset(added_to_interval, 0, sizeof(added_to_interval));
memset(data, 0, sizeof(data));
int operation;
int x;
int y;
int added_amount;
int smallest = 1;
int largest = n;
// initialize data for brute-force
for (int i = 0; i < n; ++i) {
data[i] = i + 1;
}
// build tree using array
build_tree_as_array(1, 0, n - 1);
for (int i = 0; i < number_of_operations; ++i) {
operation = rand() % 2;
x = 1 + rand() % n;
y = x + (rand() % (n - x + 1));
added_amount = 1 + rand() % n;
if (operation == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_bruteforce(x - 1, y - 1, added_amount, smallest, largest, data, n);
update_tree_as_array(1, 0, n - 1, x - 1, y - 1, added_amount);
//assert(max_tree[1] == largest);
//assert(min_tree[1] == smallest);
cout << endl << endl;
cout << "For n = " << n << endl;
// show_data(data, n);
cout << endl;
cout << " and query is " << x - 1 << ", " << y - 1 << ", " << added_amount << endl;
cout << "correct:\n";
cout << "\t largest = " << largest << endl;
cout << "\t smallest = " << smallest << endl;
cout << "testing:\n";
cout << "\t largest = " << max_tree[1] << endl;
cout << "\t smallest = " << min_tree[1] << endl;
cout << "\n------------------------------------------------------------\n";
cout << "final result: " << largest - smallest << endl;
cin.get();
}
}
cout << "DONE............\n";
}
}
int main() {
// unit_test::test_against_brute_force();
// unit_test::test_automation();
// unit_test::test_tree_as_array();
inout_range_of_data();
return 0;
}
Кажется, нет никакого преимущества в том, чтобы делать деревья сегментов ленивыми. В конце концов вам нужно будет смотреть на концы каждого сегмента наклона блока, чтобы получить минимальное и максимальное значения. Так что вы могли бы также расширить их с нетерпением.
Скорее просто измените стандартное определение дерева сегментов. Каждый интервал в дереве будет иметь дополнительное целое число d хранится с ними, поэтому мы напишем [d; lo,hi], Дерево имеет следующие операции:
init(T, hi) // make a segment tree for the interval [0; 1,hi]
split(T, x, d) // given there exists some interval [e; lo,hi],
// in T where lo < x <= hi, replace this interval
// with 2 new ones [e; lo,x-1] and [d; x,hi];
// if x==lo, then replace with [e+d; lo,hi]
Теперь после инициализации мы обрабатываем добавление d подинтервал [lo,hi] с двумя сплит операциями:
split(T, lo, d); split(T, hi+1, -d);
Идея в том, что мы добавляем d ко всему на позиции lo и вправо и вычитая его снова для hi+1 и правильно.
После того, как дерево построено, один проход слева направо через листья позволяет нам найти значения в концах целых сегментов наклона единицы. Это все, что нам нужно для вычисления минимальных и максимальных значений. Более формально, если листовые интервалы дерева [d_i; lo_i,hi_i], i=1..n в порядке слева направо, то мы хотим вычислить разность хода D_i = sum{i=1..n} d_i а потом L_i = lo_i + D_i а также H_i = hi_i + D_i, В примере мы начнем с [0; 1,10] а затем разделить на 4 с d=-4 и 7 с d=+4, чтобы получить [0; 1,2] [-4; 3,6] [4; 7,10], затем L = [1,-1,7] а также H = [2, 2, 10], Так что min равно -1, а max равно 10. Это тривиальный пример, но он будет работать в целом.
Время выполнения будет O(мин. (K log N, k^2)), где N - максимальное начальное значение диапазона (в примере 10), а k - количество примененных операций. Случай k ^ 2 возникает, если вам очень не повезло с порядком разбиений. Если вы рандомизируете список операций, ожидаемое время будет O(k min (log N, log k)).
Если вам интересно, я могу написать это для вас. Но я не буду, если нет интереса.
Вот ссылка. Он имеет реализацию и объяснение дерева сегментов с ленивым распространением. Хотя код написан на Java, но это не имеет значения, потому что есть только две функции "обновление" и "запрос", и обе они основаны на массивах. Таким образом, эти функции будут работать в C и C++ также без каких-либо изменений.
http://isharemylearning.blogspot.in/2012/08/lazy-propagation-in-segment-tree.html