线段树模板

 1 struct node
 2 {
 3     long long val;
 4     long long addmark;
 5 } ST[4*maxn+5];
 6 long long A[maxn];
 7 //修改求和还是维护区间最小值
 8 long long operation(long long a,long long b)
 9 {
10     return a+b;
11     //return max_min(a,b);
12 }
13 //修改求和还是维护区间最小值
14 void change(int pos,long long addmark,int l)
15 {
16     ST[pos].val +=addmark*l;
17 }

 1 void build(int root,int ibegin,int iend)
 2 {
 3     ST[root].addmark = 0;
 4     if (ibegin==iend)
 5         ST[root].val = A[ibegin];
 6     else
 7     {
 8         int mid = (ibegin+iend)/2;
 9         build(2*root,ibegin,mid);
10         build(2*root+1,mid+1,iend);
11         ST[root].val = operation(ST[root*2].val,ST[root*2+1].val);
12     }
13 }

 1 void push_down(int root,int l)
 2 {
 3     if (ST[root].addmark == 0) return;
 4     long long addmark = ST[root].addmark;
 5     ST[root*2].addmark+=addmark;
 6     ST[root*2+1].addmark+=addmark;
 7     change(root*2,addmark,l-l/2);
 8     change(root*2+1,addmark,l/2);
 9     ST[root].addmark = 0;
10 }

 1 long long query(int root,int ibegin,int iend,int qbegin,int qend)
 2 {
 3     if (ibegin > qend || iend < qbegin)
 4         return 0;//
 5     if (ibegin>=qbegin&&iend<=qend)
 6         return ST[root].val;
 7     push_down(root,iend-ibegin+1);
 8     int mid = (ibegin+iend)/2;
 9     return operation(query(root*2,ibegin,mid,qbegin,qend),query(root*2+1,mid+1,iend,qbegin,qend));
10 }

 1 void updata(int root,int ibegin,int iend,int qbegin,int qend,long long addmark)
 2 {
 3     if (ibegin > qend || iend < qbegin)
 4         return ;//
 5     if (ibegin>=qbegin&&iend<=qend)
 6         {
 7             ST[root].addmark+=addmark;
 8             change(root,addmark,iend-ibegin+1);
 9             return;
10         }
11     push_down(root,iend-ibegin+1);
12     int mid = (ibegin+iend)/2;
13     updata(root*2,ibegin,mid,qbegin,qend,addmark);
14     updata(root*2+1,mid+1,iend,qbegin,qend,addmark);
15     ST[root].val = operation(ST[root*2].val,ST[root*2+1].val);
16 }

总：

 1 const int maxn = 100004;
 2 struct node
 3 {
 4     long long val;
 5     long long addmark;
 6 } ST[4*maxn+5];
 7 long long A[maxn];
 8 //修改求和还是维护区间最小值
 9 long long operation(long long a,long long b)
10 {
11     return a+b;
12     //return max_min(a,b);
13 }
14 //修改求和还是维护区间最小值
15 void change(int pos,long long addmark,int l)
16 {
17     ST[pos].val +=addmark*l;
18 }
19 void build(int root,int ibegin,int iend)
20 {
21     ST[root].addmark = 0;
22     if (ibegin==iend)
23         ST[root].val = A[ibegin];
24     else
25     {
26         int mid = (ibegin+iend)/2;
27         build(2*root,ibegin,mid);
28         build(2*root+1,mid+1,iend);
29         ST[root].val = operation(ST[root*2].val,ST[root*2+1].val);
30     }
31 }
32 void push_down(int root,int l)
33 {
34     if (ST[root].addmark == 0) return;
35     long long addmark = ST[root].addmark;
36     ST[root*2].addmark+=addmark;
37     ST[root*2+1].addmark+=addmark;
38     change(root*2,addmark,l-l/2);
39     change(root*2+1,addmark,l/2);
40     ST[root].addmark = 0;
41 }
42 long long query(int root,int ibegin,int iend,int qbegin,int qend)
43 {
44     if (ibegin > qend || iend < qbegin)
45         return 0;//
46     if (ibegin>=qbegin&&iend<=qend)
47         return ST[root].val;
48     push_down(root,iend-ibegin+1);
49     int mid = (ibegin+iend)/2;
50     return operation(query(root*2,ibegin,mid,qbegin,qend),query(root*2+1,mid+1,iend,qbegin,qend));
51 }
52 void updata(int root,int ibegin,int iend,int qbegin,int qend,long long addmark)
53 {
54     if (ibegin > qend || iend < qbegin)
55         return ;//
56     if (ibegin>=qbegin&&iend<=qend)
57         {
58             ST[root].addmark+=addmark;
59             change(root,addmark,iend-ibegin+1);
60             return;
61         }
62     push_down(root,iend-ibegin+1);
63     int mid = (ibegin+iend)/2;
64     updata(root*2,ibegin,mid,qbegin,qend,addmark);
65     updata(root*2+1,mid+1,iend,qbegin,qend,addmark);
66     ST[root].val = operation(ST[root*2].val,ST[root*2+1].val);
67 }

总线段树