一维线段树

 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=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=data[l];
27         return;
28     }
29     else if(l+1==r)
30     {
31         node[2*i+1].value=data[l];
32         node[2*i+2].value=data[r];
33         node[i].value=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=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 }