两个问题，代表线段树中最基础的两类：1.更新数组里某个值然后查询。2.统一更新数组中一段区间的值然后查询。放假回来这两天也就看到了这里：）
为什么要学习线段树（个人之见）：1.如果有上万甚至更多的数据反复查找并更新，用这个数据结构就比较高效了。2.高级的数据结构和算法多学些没坏处，尤其大一大二需要注重基础。3.想考这个证书的话需要学：）
第一类问题:
成电OJ 838 母仪天下
富庶的建业城中，有一条格格不入的长街，名曰跳蚤街，被战争所致的孤儿，聚集于此。全国的经济都在为战争服务之时，也无人顾得了这里了。
除了两位夫人。
大乔小乔每天都会带着一些食物来到跳蚤街，分给某一位孩子。为了避免分配不均，她们时常会询问一个区域内食物的总量，然后进行调整以保证每个孩子都有足够的食物。
Input
第一行两个整数n，m，表示跳蚤街住着n户孩子，大乔小乔一共分发或询问了m次。
第二行n个整数，第i个数ai表示第i户孩子已有ai的食物。
接下来m行，每行开始先读入一个整数si，指明这是一次询问还是一次分发。
si=0，表明这是一次询问，然后读入两个整数li,ri，表示询问[li，ri]区间中的孩子们一共有多少食物。
si=1，表明这是一次分发，然后读入两个整数xi,wi，表示对第xi户孩子分发了wi的食物。
1≤n,m≤100000,0≤ai≤100000,1≤xi≤n,0≤wi≤10000,1≤li≤ri≤n
Output
有多少询问就输出多少行，每行输出一个整数，作为对该询问的回答。
Sample Input
5 4
1 2 3 4 5
1 2 3
0 2 4
1 4 1
0 1 5
Sample Output
12
19
#include <iostream>
#include <cstdio>
using namespace std;
typedef struct{
int l,r;
int sum;
}SegTree;
int n,m,i,j,s;
void Build(SegTree trees[], int id, int l, int r){
trees[id].l=l; trees[id].r=r;
if (l==r){
trees[id].sum=0;
}else{
int mid=(l+r)/2;
Build(trees, 1+id*2, l, mid);
Build(trees, id*2+2, mid+1, r);
trees[id].sum=trees[id*2+2].sum+trees[id*2+1].sum;
}
}
void Update(SegTree trees[], int id, int pos, int val){
if (trees[id].l==trees[id].r){
trees[id].sum=val;
}else{
int mid=(trees[id].l+trees[id].r)/2;
if (pos<=mid) Update(trees, id*2+1, pos, val);
else Update(trees, id*2+2, pos, val);
trees[id].sum=trees[id*2+2].sum+trees[id*2+1].sum;
}
}
int Query(SegTree trees[], int id, int l, int r){
if (trees[id].l==l && trees[id].r==r)
return trees[id].sum;
else{
int mid=(trees[id].l+trees[id].r)/2;
if(r<=mid) return Query(trees, id*2+1, l, r);
else if(l>mid) return Query(trees, id*2+2, l, r);
else return Query(trees, id*2+1, l, mid)+Query(trees, id*2+2, mid+1, r);
}
}
int main(){
scanf("%d%d", &n, &m);
int a[n];
SegTree *tree=new SegTree[4*n];
Build(tree, 0, 0, n-1);
for(i=0; i<n; i++){
scanf("%d", &a[i]);
Update(tree, 0, i, a[i]);
}
for(i=0; i<m; i++){
int q, ll_x, rr_w;
scanf("%d%d%d", &s, &ll_x, &rr_w);
if(s==0){
q=Query(tree, 0, ll_x-1, rr_w-1);
printf("%d\n", q);
}else{
q=Query(tree, 0, ll_x-1, ll_x-1);
Update(tree, 0, ll_x-1, rr_w+q );
}
}
return 0;
}我的数组下标是从0开始的。所以线段树的写法可能看上去和网上一些模板和伪代码不太一样。
第二类问题：
成电OJ 839 东风不与周郎便
“揽二乔于东南兮，乐朝夕之与共”
一首铜雀台赋，将愤怒与恐惧散播在了孙吴大军之中。
对抗曹军，万事俱备，只欠东风。
现在已经找到n个风眼，这些风眼的东风有强有弱，诸葛亮说他每次祈风都能够将一段风眼的东风增强，但需人去帮他布阵。同时他需要时刻掌控风眼的状况，以确定下一步的计划，所以还需要知道一段风眼的强度之和。
借东风，此乃逆天之术，施术者会折阳寿不说，布阵者更是会受十倍之伤。
“何人能当此任？”
“在下愿往，大都督。”
“你是？”
“在下一无名小卒，来自跳蚤街。”
Input
第一行两个整数n，m，表示有n个风眼，诸葛亮一共祈风或询问了m次。
第二行n个整数，第i个数ai表示第i个风眼已有东风的强度。
接下来m行，每行开始先读入一个整数si，指明这是一次询问还是一次祈风。
si=0，表明这是一次询问，然后读入两个整数li,ri，表示询问[li，ri]区间中风眼的东风强度之和。
si=1，表明这是一次祈风，然后读入三个整数li,ri,wi，表示把[li，ri]区间中每个风眼的东风强度提升wi。
1≤n,m≤100000,0≤ai≤10000,0≤wi≤10000,1≤li≤ri≤n
Output 有多少询问就输出多少行，每行输出一个整数，作为对该询问的回答。
Sample Input
5 4
1 2 3 4 5
1 2 3 2
0 3 4
1 4 5 3
0 2 4
Sample Output
9
16
手头没有一本书是讲线段树区间更新的，翻了无数博客，文档，而且网上所有资料里下标都是1开始的（很不习惯），终于写出了一个体现了C++面向对象风格的程序（其实就是把数据和操作封装了个对象-_-||）。
区间更新时并不是每个节点都更新，需要加一个标记，把要更新的数据放在标记里。等到需要修改子节点（比如更新或查询）的时候把这个标签里的信息传下去。如果你的查询或修改区间刚好和你二分处的区间相同，这个查询或修改操作就不再向下一层执行，而是直接返回结果。
#include<cstdio>
#include<cstring>
#define __int64 long long
#define MAX 100005
class Node{
public:
int l,r;
__int64 sum,add;
};
int num[MAX];
class SegTree{
private:
Node *tree;
void PushDown(int id){
int j=id*2+1;
int mid=(tree[id].l+tree[id].r)/2;
tree[j].add+=tree[id].add;
tree[j+1].add+=tree[id].add;
tree[j].sum+=tree[id].add*(mid-tree[id].l+1);
tree[j+1].sum+=tree[id].add*(tree[id].r-mid);
tree[id].add=0;
}
public:
SegTree(int n){tree=new Node[4*n];}
~SegTree(){delete []tree;}
void Build(int l,int r,int id){
tree[id].l=l; tree[id].r=r; tree[id].add=0;
if(l==r)tree[id].sum=num[l];
else{
int mid=(l+r)/2;
Build(l,mid,id*2+1);
Build(mid+1,r,id*2+2);
tree[id].sum=tree[id*2+2].sum+tree[id*2+1].sum;
}
};
void Update(int l,int r,int c,int id){
if (tree[id].l>=l&&tree[id].r<=r){
tree[id].sum+=(__int64)c*(tree[id].r-tree[id].l+1);
tree[id].add+=c;
}else{
if (tree[id].add) PushDown(id);
int mid=(tree[id].l+tree[id].r)/2;
int j=id*2+1;
if (l<=mid) Update(l,r,c,j);
if (r>mid) Update(l,r,c,j+1);
tree[id].sum=tree[j].sum+tree[j+1].sum;
}
};
__int64 Query(int l,int r,int id){
if (tree[id].l>=l && tree[id].r<=r)
return tree[id].sum;
else{
if(tree[id].add) PushDown(id);
int mid,j;
__int64 ans=0;
mid=(tree[id].l+tree[id].r)/2;
j=id*2+1;
if(l<=mid) ans+=Query(l,r,j);
if(r>mid) ans+=Query(l,r,j+1);
return ans;
}
}
};
int main(){
int n,m,a,b,c;
int cmd;
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++) scanf("%d",num+i);
SegTree tt(n);
tt.Build(0,n-1,0);
while(m--){
scanf("%d%d%d",&cmd,&a,&b);
if (cmd==1) scanf("%d",&c);
if (cmd==0)
printf("%lld\n", tt.Query(a-1, b-1, 0));
else
tt.Update(a-1, b-1, c, 0);
}
return 0;
}