首页 > 代码库 > 一维线段树

一维线段树

2024-07-16 15:03:00   217人阅读

下面是一维线段树的例子，它是建立了一棵树，叶子上的value等于在数组中下标为叶子左右节点的值。

这个题目是要求输入一个数字序列，然后输入一个区间，求出区间内的值的和。

 

 1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 const int N=1000; 5 int result; 6 struct Node 7 { 8     int left,right,value; 9 };10 Node node[N];11 int data[N];12 void build(int l,int r,int i)13 {14     node[i].left=l;15     node[i].right=r;16     node[i].value=http://www.mamicode.com/0;17     if(l==r)return;18     int mid=(l+r)>>1;19     build(l,mid,2*i+1);20     build(mid+1,r,2*i+2);21 }22 void compute(int l,int r,int i)23 {24     if(l==r)25     {26         node[i].value=http://www.mamicode.com/data[l];27         return;28     }29     else if(l+1==r)30     {31         node[2*i+1].value=http://www.mamicode.com/data[l];32         node[2*i+2].value=http://www.mamicode.com/data[r];33         node[i].value=http://www.mamicode.com/data[l]+data[r];34         return;35     }36     compute(l,node[2*i+1].right,2*i+1);37     compute(node[2*i+2].left,r,2*i+2);38     node[i].value=http://www.mamicode.com/node[2*i+1].value+node[2*i+2].value;    39 }40 void  query(int l,int r,int i)41 {42     if(node[i].left==l&&node[i].right==r)43     {44         result+=node[i].value;45         return;46     }47     if(r<=node[2*i+1].right)query(l,r,2*i+1);48     else if(l>=node[2*i+2].left)query(l,r,2*i+2);49     else 50     {51         query(l,node[2*i+1].right,2*i+1);52         query(node[2*i+2].left,r,2*i+2);53     }54 }55 int main()56 {57     int n,m;58     while(cin>>n)59     {60         build(0,n-1,0);61         for(int i=0;i<n;i++)62         cin>>data[i];63         compute(0,n-1,0);64         cin>>m;65         int a,b;66         for(int i=0;i<m;i++)67         {    68             result=0;69             cin>>a>>b;70             query(min(a-1,b-1),max(a-1,b-1),0);71             cout<<result<<endl;72         }73     }74     return 0;75 }

 


联系
我们