迭代线段树实现

Question

我指的是这个 post： 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; 
}

问题：

在 updateTreeNode 中，值被设置为父项，为什么在分配树中的值后，父级按数组大小递增？不应该是之前吗？ this post 的原始代码行是这样实现的： for (tree[parent += n] = value; parent > 1; parent >>= 1) 其中 parent=parent+n 首先执行。谁能帮我理解为什么这段代码仍然正常运行？

Within query which returns 区间[l, r)中的一个和，这段代码好像加了结果仅适用于 l 的奇数值。然而，我看到结果正确 returns 偶值区间的总和。

由于没有else <accumulate result>，结果应该是跳过累积偶值区间，对吧？我错过了什么？

Answer 1

问题 1

变量p并不意味着parent，它意味着child。在for循环中，i是child节点，我们更新i的parent.

的值

tree[p+n] = value;：更新离开节点（没有children的节点）的值。然后我们从离开节点更新节点 parent 的值。 tree[i>>1] = tree[i] + tree[i^1];, tree[i>>1] 是 tree[i]' parent.

例如：数组大小为16（树大小为32）我想更新arr[8]。所以我调用updateTreeNode(8, value)。首先更新three[8+16]，对应arr[8]。然后p设置为24。在for循环中，我们更新p的parent（树[12]），然后设置p为p/2（p=12），直到p不有 parent.

问题 2

如果l和r是偶数，我们在下一次循环中添加parent的值。这就是线段树的作用，避免查询区间内的每个元素。

例如：数组大小为16，我想查询[8,10)。在线段树中，区间为[24,26)。我们不需要添加 tree[24] 和 tree[25] 的值，我们添加 tree[12]!

的值

迭代线段树实现

Iterative segment tree implmentation

c++

algorithm

tree

data-structures

segment-tree

问题 1

问题 2