Итеративная сегментация дерева - PullRequest
Новая
       33

Итеративная сегментация дерева

0 голосов
/ 10 апреля 2020

Я имею в виду этот пост: https://www.geeksforgeeks.org/segment-tree-efficient-implementation/

Вставка кода здесь для справки. Мои вопросы находятся под кодом. 

#include <bits/stdc++.h> 
using namespace std; 

// limit for array size 
const int N = 100000; 

int n; // array size 

// Max size of tree 
int tree[2 * N]; 

// function to build the tree 
void build( int arr[]) 
{ 
    // insert leaf nodes in tree 
    for (int i=0; i<n; i++)  
        tree[n+i] = arr[i]; 

    // build the tree by calculating parents 
    for (int i = n - 1; i > 0; --i)  
        tree[i] = tree[i<<1] + tree[i<<1 | 1];   
} 

// function to update a tree node 
void updateTreeNode(int p, int value) 
{ 
    // set value at position p 
    tree[p+n] = value;              // {Question} Why is this assigned before updating the parent index to access?
    p = p+n;

    // move upward and update parents 
    for (int i=p; i > 1; i >>= 1) 
        tree[i>>1] = tree[i] + tree[i^1]; 
} 

// function to get sum on interval [l, r) 
int query(int l, int r) 
{ 
    int res = 0; 

    // loop to find the sum in the range 
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) 
    { 
        if (l&1) 
            res += tree[l++]; 

        if (r&1) 
            res += tree[--r];
        // {Question} What happens if !(l&1) or !(r&1) ? res is not accumulated anywhere. Isn't this wrong?
    } 


    return res; 
} 

// driver program to test the above function 
int main() 
{ 
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; 

    // n is global 
    n = sizeof(a)/sizeof(a[0]); 

    // build tree 
    build(a); 

    // print the sum in range(1,2) index-based 
    cout << query(1, 3)<<endl; 

    // modify element at 2nd index 
    updateTreeNode(2, 1); 

    // print the sum in range(1,2) index-based 
    cout << query(1, 3)<<endl; 

    return 0; 
}

Вопросы:

  1. В пределах updateTreeNode, где значение устанавливается на parent, почему родительский элемент увеличивается на массив размер после присвоение значения в дереве? Не должно ли быть раньше? Оригинальная строка кода в этом посте реализована следующим образом: for (tree[parent += n] = value; parent > 1; parent >>= 1), где parent=parent+n выполняется первым. Может кто-нибудь помочь мне понять, почему этот код по-прежнему функционирует должным образом?

  2. В пределах query, который возвращает сумму в интервале [l, r), этот код добавляет результат только для нечетные значения l. Тем не менее, я вижу, что результат правильно возвращает сумму для четных интервалов.

    Результат должен пропускать накопление четных интервалов, поскольку else <accumulate result> нет, верно? Чего мне не хватает?

1 Ответ

0 голосов
/ 10 апреля 2020

Вопрос 1

Переменная p не означает родителя, она означает ребенка. В for l oop, i является дочерним узлом, и мы обновляем значение родительского элемента i.

tree[p+n] = value;: обновляем значение покидающего узла (узла без дочерних элементов). Затем мы обновляем значение родителя узла с узла отпуска. tree[i>>1] = tree[i] + tree[i^1];, tree[i>>1] является tree[i] 'родительским.

Например: размер массива равен 16 (размер дерева равен 32), и я хочу обновить arr [8]. Поэтому я звоню updateTreeNode(8, value). Сначала обновляется three[8+16], что соответствует arr[8]. Тогда p устанавливается на 24. В течение l oop мы обновляем родительский элемент p (дерево [12]), затем устанавливаем p на p / 2 (p = 12), пока p не будет иметь родителя.

Quration 2

Если l и r четные, мы добавляем значение родителя в следующем повторении. Это функция дерева сегментов, чтобы не запрашивать каждый элемент в интервале.

Например: размер массива равен 16, и я хочу сделать запрос [8,10). В сегментном дереве интервал составляет [24,26). Нам не нужно добавлять значения tree[24] и tree[25], мы добавляем значение tree[12]!

...