【数据结构】线段树（Segment Tree）

?

#include<bits/stdc++.h>
using namespace std; const int N = 1000; int a[] = {1,3,5,7,9,11}; int size = 6; int tree[N] = {0}; //建立范围为a[start]~a[end] 
void build(int a[],int tree[],int node/*当前节点*/,int start,int end){ //递归边界(即遇到叶子节点时) 
    if (start == end){ //直接存储a数组中的值 
        tree[node] = a[start]; } else { //将建立的区间分成两半 
        int mid = (start + end) / 2; int left  = 2 * node + 1;//左子节点的下标 
        int right = 2 * node + 2;//右子节点的下标 //求出左子节点的值(即从节点left开始,建立范围为a[start]~a[mid])
 build(a,tree,left,start,mid); //求出右子节点的值(即从节点right开始,建立范围为a[start]~a[mid])
        build(a,right,mid+1,end); //当前节点的职位左子节点的值加上右子节点的值 
        tree[node] = tree[left] + tree[right]; } } int main(){ //从根节点(即节点0)开始建树,建树范围为a[0]~a[size-1]
    build(a,0,size-1); for(int i = 0; i <= 14; i ++) printf("tree[%d] = %dn",i,tree[i]); return 0; }

运行结果：

update操作：

• 确定需要改的分支，向下寻找需要修改的节点，再向上修改节点值。
• ?与建树的函数相比，update函数增加了两个参数x，val，即把a[x]改为val。

例：把a[x]改为6（代码实现）

（编辑：辽源站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!