线段树的基本操作

点更新：

 1 #include <fstream>                 //点更新
 2 #include <iostream>
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 
 7 const int N=10000;
 8 int n,m,a[N];
 9 struct node
10 {
11     int left,right;
12     int max_,sum_;
13 }tree[4*N];
14 
15 void build(int id,int l,int r);//建一棵线段树
16 int query_sum(int id,int l,int r);//查询区间和
17 int query_max(int id,int l,int r);//查询区间最大值
18 void update(int id,int pos,int val);//更新位置pos的值增加val
19 
20 int main()
21 {
22     //freopen("D:\input.in","r",stdin);
23     //freopen("D:\output.out","w",stdout);
24     int bo,t1,t2;
25     scanf("%d%d",&n,&m);
26     for(int i=1;i<=n;i++)
27         scanf("%d",&a[i]);
28     build(1,1,n);
29     for(int i=1;i<=m;i++)
30     {
31         scanf("%d%d%d",&bo,&t1,&t2);
32         if(bo)//更新(这里指增加)
33             update(1,t1,t2);
34         else
35             printf("%d
",query_sum(1,t1,t2));
36     }
37     return 0;
38 }
39 void build(int id,int l,int r)
40 {
41     tree[id].left=l;
42     tree[id].right=r;
43     if(l==r)
44     {
45         tree[id].sum_=a[l];
46         tree[id].max_=a[l];
47     }
48     else
49     {
50         int mid=(l+r)/2;
51         build(2*id,l,mid);
52         build(2*id+1,mid+1,r);
53         tree[id].sum_=tree[2*id].sum_+tree[2*id+1].sum_;
54         tree[id].max_=max(tree[2*id].max_,tree[2*id+1].max_);
55     }
56 }
57 int query_sum(int id,int l,int r)
58 {
59     if(tree[id].left==l&&tree[id].right==r)
60         return tree[id].sum_;
61     else
62     {
63         int mid=(tree[id].left+tree[id].right)/2;
64         if(r<=mid)  return query_sum(2*id,l,r);
65         else if(l>mid)  return query_sum(2*id+1,l,r);
66         else
67             return query_sum(2*id,l,mid)+query_sum(2*id+1,mid+1,r);
68     }
69 }
70 int query_max(int id,int l,int r)
71 {
72     if(tree[id].left==l&&tree[id].right==r)
73         return tree[id].max_;
74     else
75     {
76         int mid=(tree[id].left+tree[id].right)/2;
77         if(r<=mid)  return query_max(2*id,l,r);
78         else if(l>mid)  return query_max(2*id+1,l,r);
79         else
80             return max(query_max(2*id,l,mid),query_max(2*id+1,mid+1,r));
81     }
82 }
83 void update(int id,int pos,int val)
84 {
85     if(tree[id].left==tree[id].right)
86     {
87         tree[id].sum_+=val;//假如修改而不是增加，就把+=改为=。
88         tree[id].max_+=val;
89     }
90     else
91     {
92         int mid=(tree[id].left+tree[id].right)/2;
93         if(pos<=mid)    update(2*id,pos,val);
94         else update(2*id+1,pos,val);
95         tree[id].sum_=tree[2*id].sum_+tree[2*id+1].sum_;
96         tree[id].max_=max(tree[2*id].max_,tree[2*id+1].max_);
97     }
98 }

View Code

区间更新：

  1 #include <fstream>
  2 #include <iostream>
  3 #include <cstdio>
  4 
  5 using namespace std;
  6 
  7 const int N=100005;
  8 int n,m,a[N];
  9 struct node
 10 {
 11     int left,right;
 12     long long lazy,sum_;
 13 }tree[4*N];
 14 
 15 void build(int id,int l,int r);//建一棵线段树
 16 long long query_sum(int id,int l,int r);//查询区间和
 17 void update(int id,int p1,int p2,int val);//更新区间[p1,p2]的值增加val
 18 
 19 int main()
 20 {
 21     //freopen("D:\input.in","r",stdin);
 22     //freopen("D:\output.out","w",stdout);
 23     int bo,t1,t2,t3;
 24     scanf("%d%d",&n,&m);
 25     for(int i=1;i<=n;i++)
 26         scanf("%d",&a[i]);
 27     build(1,1,n);
 28     for(int i=1;i<=m;i++)
 29     {
 30         scanf("%d%d%d",&bo,&t1,&t2);
 31         if(bo)//更新(这里指增加)
 32         {
 33             scanf("%d",&t3);
 34             update(1,t1,t2,t3);
 35         }
 36         else
 37             printf("%lld
",query_sum(1,t1,t2));
 38     }
 39     return 0;
 40 }
 41 void build(int id,int l,int r)
 42 {
 43     tree[id].left=l;
 44     tree[id].right=r;
 45     tree[id].lazy=0;
 46     if(l==r)
 47     {
 48         tree[id].sum_=a[l];
 49     }
 50     else
 51     {
 52         int mid=(l+r)/2;
 53         build(2*id,l,mid);
 54         build(2*id+1,mid+1,r);
 55         tree[id].sum_=tree[2*id].sum_+tree[2*id+1].sum_;
 56     }
 57 }
 58 long long query_sum(int id,int l,int r)
 59 {
 60     if(tree[id].left==l&&tree[id].right==r)
 61         return tree[id].sum_;
 62     else
 63     {
 64         int mid=(tree[id].left+tree[id].right)/2;
 65         if(tree[id].lazy)
 66         {
 67             update(2*id,tree[id].left,mid,tree[id].lazy);
 68             update(2*id+1,mid+1,tree[id].right,tree[id].lazy);
 69             tree[id].lazy=0;
 70         }
 71         if(r<=mid)  return query_sum(2*id,l,r);
 72         else if(l>mid)  return query_sum(2*id+1,l,r);
 73         else
 74             return query_sum(2*id,l,mid)+query_sum(2*id+1,mid+1,r);
 75     }
 76 }
 77 void update(int id,int p1,int p2,int val)
 78 {
 79     if(tree[id].left==p1&&tree[id].right==p2)
 80     {
 81         tree[id].lazy+=val;
 82         tree[id].sum_+=val*(p2-p1+1);
 83     }
 84     else
 85     {
 86         int mid=(tree[id].left+tree[id].right)/2;
 87         if(tree[id].lazy)
 88         {
 89             update(2*id,tree[id].left,mid,tree[id].lazy);
 90             update(2*id+1,mid+1,tree[id].right,tree[id].lazy);
 91             tree[id].lazy=0;
 92         }
 93         if(p2<=mid)
 94             update(2*id,p1,p2,val);
 95         else if(p1>mid)
 96             update(2*id+1,p1,p2,val);
 97         else
 98         {
 99             update(2*id,p1,mid,val);
100             update(2*id+1,mid+1,p2,val);
101         }
102         tree[id].sum_=tree[2*id].sum_+tree[2*id+1].sum_;
103     }
104 }

View Code

需要注意的是：线段树空间应开为原数组长度的4倍。

空间复杂度~O(N*4)，每次更新和查询操作的复杂度都是O(logN)。