在C++中构建分段树

我正在尝试在C++中构建分段树。以下为相同的递归函数：在C++中构建分段树

int buildTree(int node,int start,int end,int tree[]) 
{ 
     // printf("Node is: %d\n",node); 
    printf("start: %d\tend:%d\tnode:%d\t\n",start,end,node); 
    if (start == end) 
    { 
     // printf("start: %d,node: %d,array[start] : %d\n",start,node,array[start]); 
     tree[node] = array[start]; 
     return array[start]; 

    } 
    else 
    { 
     int mid = (start + end)/2; 

     buildTree(2 * node ,mid + 1,end,tree); 
     buildTree(2 * node + 1,start,mid,tree); 

     tree[node] = tree[ 2 * node ] + tree[ 2 * node + 1 ]; 
     return tree[node]; 
    } 
}

该阵列是全局定义：

int array[] = {1,2,3,4,5};

以下调用后的树：

int main(int argc, char const *argv[]) 
{ 
    int tree[100]; 
    buildTree(0,0,4,tree); 
    for (int i = 0; i < 9; ++i) 
    { 
     printf("%d : %d\n",i, tree[i]); 
    } 
    return 0; 
}

给出了输出：

start: 0 end:4 node:0 
start: 3 end:4 node:0 
start: 4 end:4 node:0 
start: 3 end:3 node:1 
start: 0 end:2 node:1 
start: 2 end:2 node:2 
start: 0 end:1 node:3 
start: 1 end:1 node:6 
start: 0 end:0 node:7 
0 : 15 
1 : 6 
2 : 3 
3 : 3 
4 : 474810352 
5 : 32766 
6 : 2 
7 : 1 
8 : 0

因此，th e节点4和5从不处理。我在哪里做错了？我觉得我在递归方面很难。

来源

2017-06-18 learner

解决这些问题的正确工具是你的调试器。在*堆栈溢出问题之前，您应该逐行执行您的代码。如需更多帮助，请阅读[如何调试小程序（由Eric Lippert撰写）]（https://ericlippert.com/2014/03/05/how-to-debug-small-programs/）。至少，你应该[编辑]你的问题，以包含一个[Minimal，Complete，and Verifiable]（http://stackoverflow.com/help/mcve）例子来重现你的问题，以及你在调试器中所做的观察。 –

您正在一遍一遍地构建'node [0]'b/c'2 * 0 == 0'。 –

我该如何避免这种情况？ – learner

我使用某种方式构建了一个段树，使用相同的实现。

你应该调用该函数buildTree初始节点= 1

buildTree(1,0,4,tree);

这应该修正这个错误。

而且大部分的段树实现码使用的节点（2 *节点）的范围（开始 - >中期）和所述节点（2 *节点+ 1）的范围（中间+ 1 - >结束）。

我认为这是一个约定的问题。但是坚持使用约定会让你更容易调试你的代码，并且更容易让其他程序员理解它。

所以你可以重写递归调用为：

buildTree(2 * node ,start,mid,tree); 
buildTree(2 * node + 1,mid+1,end,tree);

相反的：

buildTree(2 * node ,mid + 1,end,tree); 
buildTree(2 * node + 1,start,mid,tree);

来源

2017-06-18 09:29:25

在C++中构建分段树

回答

相关问题