Подтвердить что ты не робот

Как реализовать деревья сегментов с ленивым распространением?

Я искал в Интернете о реализации деревьев сегментов, но ничего не нашел, когда дело дошло до ленивого распространения. Были некоторые предыдущие вопросы о переполнении стека, но они были сосредоточены на решении некоторых конкретных проблем SPOJ. Хотя я думаю, что это лучшее объяснение деревьев сегментов с псевдокодом, но мне нужно реализовать его с ленивым распространением. Я нашел следующие ссылки:

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Segment_Trees

В дополнение к вышеуказанной ссылке некоторые блоги также были там, но все они ссылались на один и тот же поток.

Пример

пример приложения этой структуры данных будет что-то вроде, скажем, мне дали диапазон чисел от 1 до n. Теперь я выполняю некоторые операции, такие как добавление некоторого постоянного числа в определенный диапазон или вычитание некоторого постоянного числа из определенного диапазона. После выполнения операций я должен указать минимальное и максимальное число в указанном номере.

Очевидным решением будет выполнение сложения или вычитания каждого числа в заданном диапазоне один за другим. Но это не может быть осуществимо в ситуации, когда никакие операции не являются большими.

A лучший подход будет использовать сегментные деревья с ленивой технологией распространения. Он говорит вместо того, чтобы выполнять операцию обновления по каждому номеру отдельно, просто отслеживайте все операции до тех пор, пока все операции не будут выполнены. Затем, наконец, выполните операцию обновления, чтобы получить минимальное и максимальное число в диапазоне.

Пример с реальными данными

Предположим, что я дал диапазон [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

Это простой пример. Фактическая проблема может содержать тысячи таких операций сложения/вычитания. Надеюсь, теперь это ясно.

Это то, что я понял до сих пор, но я думаю, что в Интернете нет единой ссылки, которая лучше объясняет концепцию и реализацию.

Может ли кто-нибудь дать хорошее объяснение, включая псевдокод для ленивого распространения в деревьях сегментов?

Спасибо.

4b9b3361

ОТВЕТЫ

Ответ 1

Ленивое распространение почти всегда включает какой-то часовой механизм. Вы должны убедиться, что текущий node не нужно распространять, и эта проверка должна быть простой и быстрой. Таким образом, есть две возможности:

  • Пожертвуйте немного памяти, чтобы сохранить поле в node, которое можно легко проверить.
  • Пожертвуйте немного времени выполнения, чтобы проверить, был ли распространен node, и должны ли быть созданы его дочерние узлы.

Я придерживался первого. Очень просто проверить, должен ли node в сегментированном дереве иметь дочерние узлы (node->lower_value != node->upper_value), но вам также нужно будет проверить, уже ли эти дочерние node (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;

Инициализация

Для инициализации node мы вызываем initialize указателем на указатель node (или 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;
}

Доступ

Пока ничего особенного не сделано. Это похоже на любой другой общий метод создания node. Однако, чтобы создать фактические дочерние узлы и установить флаги распространения, мы можем использовать функцию, которая вернет указатель на тот же node, но при необходимости распространяет его:

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;
}

Как вы можете видеть, распространяемый node почти сразу выйдет из функции. Нераспространяемый node вместо этого сначала проверяет, должен ли он фактически содержать дочерние узлы, а затем создавать их при необходимости.

Это на самом деле ленивая оценка. Вы не создаете дочерние узлы до тех пор, пока это не понадобится. Обратите внимание, что accessErr также предоставляет дополнительный интерфейс ошибок. Если вам это не нужно, используйте access вместо:

lazy_segment_node * access(lazy_segment_node* node){
  return accessErr(node,NULL);
}

Free

Чтобы освободить эти элементы, вы можете использовать общий алгоритм deallocation node:

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 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)

Lazy evaluation test
test->lower_value: 1
test->upper_value: 10

Node not propagated
test->left_child: (nil)
test->right_child: (nil)

Node propagated with access:
access(test)->left_child: 0x948e020
access(test)->right_child: 0x948e038

Node propagated with access, but subchilds are not:
access(test)->left_child->left_child: (nil)
access(test)->left_child->right_child: (nil)

Can use access on subchilds:
access(test->left_child)->left_child: 0x948e050
access(test->left_child)->right_child: 0x948e068

It possible to chain:
access(access(access(test)->right_child)->right_child)->lower_value: 9
access(access(access(test)->right_child)->right_child)->upper_value: 10

Ответ 2

Хотя я еще не успел его решить, я считаю, что эта проблема намного проще, чем мы думаем. Вам, вероятно, даже не нужно использовать Дерево сегментов/Дерево интервалов... На самом деле, я пробовал оба варианта реализации Segment Tree, один использует древовидную структуру, а другой использует массив, оба решения быстро получили TLE. У меня такое чувство, что это можно сделать с помощью Greedy, но я еще не уверен. Во всяком случае, если вы хотите увидеть, как все это делается с помощью Segment Tree, не стесняйтесь изучать мое решение. Обратите внимание, что 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;
}

Ответ 3

Кажется, нет никакого преимущества в том, чтобы деревья сегментов были ленивыми. В конце концов вам нужно будет посмотреть на концы каждого сегмента сегмента юнита, чтобы получить минимальное и максимальное значение. Так что вы могли бы также расширить их с нетерпением.

Скорее просто измените стандартное определение дерева сегментов. У интервалов в дереве будет храниться дополнительное целое число 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 в subinterval [lo,hi] с двумя разделенными операциями:

split(T, lo, d); split(T, hi+1, -d);

Идея здесь заключается в том, что мы добавляем d ко всему в позиции lo и вправо и вычитаем ее снова для hi+1 и right.

После того, как дерево построено, один левый-правый проход по листьям позволяет нам находить значения на концах сегментов единичного наклона целых чисел. Это все, что нам нужно для вычисления значений min и max. Более формально, если листовые интервалы дерева [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 (min (k log N, k ^ 2)), где N - максимальное начальное значение диапазона (10 в примере), а k - количество примененных операций. Случай k ^ 2 возникает, если вам очень не повезло в упорядочении расколов. Если вы производите список операций, ожидаемое время будет O (k min (log N, log k)).

Если вы заинтересованы, я могу запрограммировать это для вас. Но я не буду, если не будет интереса.

Ответ 4

Здесь ссылка. Он имеет реализацию и объяснение дерева сегментов с ленивым распространением. Хотя код находится на Java, но это не имеет значения, потому что есть только две функции "обновление" и "запрос", и оба они основаны на массиве. Таким образом, эти функции будут работать и на C и С++ без каких-либо изменений.

http://isharemylearning.blogspot.in/2012/08/lazy-propagation-in-segment-tree.html

Ответ 5

если кто-то ищет более простой код ленивого распространения без использования структур:

(код не требует пояснений)

/**
 * 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]
}

ссылайтесь на эту ссылку для получения дополнительной информации Сегментные деревья и ленивое распространение