Обновление в дереве сегментов

Итак, необходимо эффективно обновлять интервал [L,R] с соответствующими значениями арифметической прогрессии с шагом X и иметь возможность эффективно находить суммы по различным интервалам.

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

Основные идеи следующие:

• Арифметическая прогрессия может быть определена элементами first и last и amount of items.

• Можно получить новую арифметическую прогрессию, комбинируя элементы first и last двух разных арифметических прогрессий (которые имеют одинаковое количество элементов). Элементы first и last новой арифметической прогрессии будут просто комбинацией соответствующих элементов комбинированных арифметических прогрессий.

• Следовательно, мы можем связать с каждым узлом дерева сегментов значения first и last арифметической прогрессии, охватывающей заданный интервал.

• Во время обновления для всех затронутых интервалов мы можем лениво распространять по дереву сегментов значения элементов first и last и обновлять агрегированные суммы по этим интервалам.

Итак, узел дерева сегментов для данной задачи будет иметь структуру:

class Node {
    int left; // Left boundary of the current SegmentTree node
    int right; // Right boundary of the current SegmentTree node

    int sum; // Sum on the interval [left,right]

    int first; // First item of arithmetic progression inside given node
    int last; // Last item of arithmetic progression

    Node left_child;
    Node right_child;

    // Constructor
    Node(int[] arr, int l, int r) { ... }

    // Add arithmetic progression with step X on the interval [l,r]
    // O(log(N))
    void add(int l, int r, int X) { ... }

    // Request the sum on the interval [l,r]
    // O(log(N))
    int query(int l, int r) { ... }

    // Lazy Propagation
    // O(1)
    void propagate() { ... }
}

Специфика дерева сегментов с отложенным распространением такова, что каждый раз при обходе узла дерева выполняется процедура отложенного распространения (со сложностью O(1)). для данного узла. Итак, ниже приведена иллюстрация логики Lazy Propagation для некоторого произвольного узла, у которого есть дочерние элементы:

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

Реализация

Ниже представлена ​​Java-реализация описанного подхода (с дополнительными комментариями):

class Node {
    int left; // Left boundary of the current SegmentTree node
    int right; // Right boundary of the current SegmentTree node
    int sum; // Sum on the interval
    int first; // First item of arithmetic progression
    int last; // Last item of arithmetic progression
    Node left_child;
    Node right_child;

    /**
     * Construction of a Segment Tree
     * which spans over the interval [l,r]
     */
    Node(int[] arr, int l, int r) {
        left = l;
        right = r;
        if (l == r) { // Leaf
            sum = arr[l];
        } else { // Construct children
            int m = (l + r) / 2;
            left_child = new Node(arr, l, m);
            right_child = new Node(arr, m + 1, r);
            // Update accumulated sum
            sum = left_child.sum + right_child.sum;
        }
    }

    /**
     * Lazily adds the values of the arithmetic progression
     * with step X on the interval [l, r]
     * O(log(N))
     */
    void add(int l, int r, int X) {
        // Lazy propagation
        propagate();
        if ((r < left) || (right < l)) {
            // If updated interval doesn't overlap with current subtree
            return;
        } else if ((l <= left) && (right <= r)) {
            // If updated interval fully covers the current subtree
            // Update the first and last items of the arithmetic progression
            int first_item_offset = (left - l) + 1;
            int last_item_offset = (right - l) + 1;
            first = X * first_item_offset;
            last = X * last_item_offset;
            // Lazy propagation
            propagate();
        } else {
            // If updated interval partially overlaps with current subtree
            left_child.add(l, r, X);
            right_child.add(l, r, X);
            // Update accumulated sum
            sum = left_child.sum + right_child.sum;
        }
    }

    /**
     * Returns the sum on the interval [l, r]
     * O(log(N))
     */
    int query(int l, int r) {
        // Lazy propagation
        propagate();
        if ((r < left) || (right < l)) {
            // If requested interval doesn't overlap with current subtree
            return 0;
        } else if ((l <= left) && (right <= r)) {
            // If requested interval fully covers the current subtree
            return sum;
        } else {
            // If requested interval partially overlaps with current subtree
            return left_child.query(l, r) + right_child.query(l, r);
        }
    }

    /**
     * Lazy propagation
     * O(1)
     */
    void propagate() {
        // Update the accumulated value
        // with the sum of Arithmetic Progression
        int items_count = (right - left) + 1;
        sum += ((first + last) * items_count) / 2;
        if (right != left) { // Current node is not a leaf
            // Calculate the step of the Arithmetic Progression of the current node
            int step = (last - first) / (items_count - 1);
            // Update the first and last items of the arithmetic progression
            // inside the left and right subtrees
            // Distribute the arithmetic progression between child nodes
            // [a(1) to a(N)] -> [a(1) to a(N/2)] and [a(N/2+1) to a(N)]
            int mid = (items_count - 1) / 2;
            left_child.first += first;
            left_child.last += first + (step * mid);
            right_child.first += first + (step * (mid + 1));
            right_child.last += last;
        }
        // Reset the arithmetic progression of the current node
        first = 0;
        last = 0;
    }
}

Дерево сегментов в предоставленном решении реализовано явно - с использованием объектов и ссылок, однако его можно легко изменить, чтобы вместо этого использовать массивы.

Тестирование

Ниже представлены рандомизированные тесты, в которых сравниваются две реализации:

• Обработка запросов путем последовательного увеличения каждого элемента массива с O(N) и вычисления сумм на интервалах с O(N)
• Обработка тех же запросов с помощью дерева сегментов со сложностью O(log(N)):

Java-реализация рандомизированных тестов:

public static void main(String[] args) {
    // Initialize the random generator with predefined seed,
    // in order to make the test reproducible
    Random rnd = new Random(1);

    int test_cases_num = 20;
    int max_arr_size = 100;
    int num_queries = 50;
    int max_progression_step = 20;

    for (int test = 0; test < test_cases_num; test++) {
        // Create array of the random length
        int[] arr = new int[rnd.nextInt(max_arr_size) + 1];
        Node segmentTree = new Node(arr, 0, arr.length - 1);

        for (int query = 0; query < num_queries; query++) {
            if (rnd.nextDouble() < 0.5) {
                // Update on interval [l,r]
                int l = rnd.nextInt(arr.length);
                int r = rnd.nextInt(arr.length - l) + l;
                int X = rnd.nextInt(max_progression_step);
                update_sequential(arr, l, r, X); // O(N)
                segmentTree.add(l, r, X); // O(log(N))
            }
            else {
                // Request sum on interval [l,r]
                int l = rnd.nextInt(arr.length);
                int r = rnd.nextInt(arr.length - l) + l;
                int expected = query_sequential(arr, l, r); // O(N)
                int actual = segmentTree.query(l, r); // O(log(N))
                if (expected != actual) {
                    throw new RuntimeException("Results are different!");
                }
            }
        }
    }
    System.out.println("All results are equal!");
}

static void update_sequential(int[] arr, int left, int right, int X) {
    for (int i = left; i <= right; i++) {
        arr[i] += X * ((i - left) + 1);
    }
}

static int query_sequential(int[] arr, int left, int right) {
    int sum = 0;
    for (int i = left; i <= right; i++) {
        sum += arr[i];
    }
    return sum;
}

По сути, вам нужно создать дерево, а затем делать обновления, используя ленивое распространение, вот реализация.

int tree[1 << 20], Base = 1 << 19;
int lazy[1 << 20];
void propagation(int v){ //standard propagation
  tree[v * 2] += lazy[v];
  tree[v * 2 + 1] += lazy[v];
  lazy[v * 2] += lazy[v];
  lazy[v * 2 + 1] += lazy[v];
  lazy[v] == 0;
}
void update(int a, int b, int c, int v = 1, int p = 1, int k = Base){
  if(p > b || k < a) return; //if outside range [a, b]
  propagation(v);
  if(p >= a && k <= b){ // if fully inside range [a, b]
    tree[v] += c;
    lazy[v] += c;
    return;
  }
  update(a, b, c, v * 2, p, (p + k) / 2); //left child
  update(a, b, c, v * 2 + 1, (p + k) / 2 + 1, k); //right child
  tree[v] = tree[v * 2] + tree[v * 2 + 1]; //update current node
}
int query(int a, int b, int v = 1, int p = 1, int k = Base){
  if(p > b || k < a) //if outside range [a, b]
    return 0;
  propagation(v);
  if(p >= a && k <= b) // if fully inside range [a, b]
    return tree[v];
  int res = 0;
  res += query(a, b, c, v * 2, p, (p + k) / 2); //left child
  res += query(a, b, c, v * 2 + 1, (p + k) / 2 + 1, k); //right child
  tree[v] = tree[v * 2] + tree[v * 2 + 1]; //update current node
  return res;
}

функция обновления автоматически обновляет дерево, поэтому оно добавляется к узлам на интервале [a, b] (или [L, R])

update(L, R, value);

функция запроса просто дает вам сумму элементов в диапазоне

query(L, R);