线段树

数组：
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 
 6 using namespace std;
 7 const int N=1001;
 8 
 9 int a[N];
10 int sum[N];
11 
12 void rushu(int jd)
13 {
14     sum[jd]=sum[jd<<1]+sum[jd<<1+1];
15 }
16 
17 void built(int l,int r,int jd)
18 {
19     if(l==r)
20     {
21         sum[jd]=a[l];
22         return ; 
23     }
24     int mid=(l+r)>>1;
25     built(1,mid,jd<<1);
26     built(mid+1,r,jd<<2);
27     rushu(jd);
28 }
29 
30 void gai(int l,int r,int jd,int q,int v)
31 {
32     if(l==r)
33     {
34         sum[jd]=v;
35         return ;
36     }
37     int mid=(l+r)>>1;
38     if(q<mid)gai(l,mid,jd<<1,q,v);
39     if(q>mid)gai(mid+1,r,jd<<1+1,q,v);
40     rushu(jd);
41 }
42 
43 int js(int l,int r,int jd,int nl,int nr)
44 {
45     if(nl<l&&nr<r)
46     {
47         return sum[jd];
48     }
49     int mid=(l+r)>>1;
50     int ans=0;
51     if(mid>nl)ans+=js(l,mid,jd*2,nl,nr);
52     if(mid<nr)ans+=js(mid+1,r,jd*2+1,nl,nr);
53     return ans;
54 }
55 
56 void built(int l,int r,int jd)
57 {
58     if(l==r)
59     {
60         sum[jd]=a[l];
61         return ;
62     }
63     int mid=(l+r)>>1;
64     built(l,mid,jd<<1);
65     built(mid+1,r,jd<<1+1);
66     rushu(jd);
67 }
68 
69 
70 
71 int main()
72 {
73     int n,m;//built ,js ,gai ,ts
74     cin>>n>>m;
75     for(int i=1;i<=n;i++)
76     {
77         cin>>a[i];
78     }
79     
80     built(1,n,1);
81     
82     int _,__;
83     cin>>_>>__;
84     
85     gai(1,n,1,_,__);
86     
87     int ___,____;
88     cin>>___>>____;
89     js(1,n,1,___,____);
90     
91     return 0;
92 }

结构体：

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 const int N=100001;
 6 
 7 int ans,n,m,x,y,z;
 8 
 9 struct node{
10     int l,r,w;
11 }T[N];
12 
13 inline void build(int l,int r,int jd)
14 {
15     T[jd].l=l;
16     T[jd].r=r;
17     if(l==r)
18     {
19         cin>>T[jd].w;
20         return ;
21     }
22     int mid=(l+r)>>1;
23     build(l,mid,jd<<1);
24     build(mid+1,r,jd<<1|1);
25     T[jd].w=T[jd<<1].w+T[jd<<1|1].w;
26 }
27 
28 inline void add(int jd)
29 {
30     if(T[jd].l==T[jd].r)
31     {
32         T[jd].w+=z;
33         return ;
34     }
35     int mid=(T[jd].l+T[jd].r)/2;
36     if(y<=mid)
37     {
38         add(jd<<1);
39     }
40     else
41     {
42         add(jd<<1|1);
43     }
44     T[jd].w=T[jd<<1].w+T[jd<<1|1].w;
45 }
46 
47 inline void sum(int jd)
48 {
49     if(y<=T[jd].l&&T[jd].r<=z)
50     {
51         ans+=T[jd].w;
52         return ;
53     }
54     int mid=(T[jd].l+T[jd].r)/2;
55     if(y<=mid)
56     {
57         sum(jd*2);
58     }
59     if(z>mid)
60     {
61         sum(jd*2+1);
62     }
63 }
64 
65 int main()
66 {
67     cin>>n;
68     build(1,n,1);
69     cin>>m;
70     for(int i=1;i<=m;i++)
71     {
72         cin>>x>>y>>z;
73         ans=0;
74         if(x==1)
75         {
76             add(1);
77         }
78         else
79         {
80             sum(1);
81             cout<<ans<<endl;
82         }
83     }
84 }