线段树分配空间大小问题

2017-03-13 96点热度 0人点赞

不要左右节点指针,用一个数组存放线段树。根节点下标为0。假设线段树上某节点下标为i,则:左子节点下标为i*2+1, 右子节点下标为i*2+2如果用一维数组存放线段树,且根节点区间[1,n]
使用左右节点指针,则数组需要有2n-1个元素

不使用左右节点指针,则数组需要有:2*2^ [log2n] -1个元素([log2n]向上取整) 2*2^ [log2n] -1 <= 4n -1 , 实际运用时常可以更小,可尝试3n

个人觉得还是用4n保险

未经允许不得转载!线段树分配空间大小问题

本文地址:https://ai.52learn.online/680

站长邮箱:ai52learn@foxmail.com