线段树模板
就去年暑假的时候老师讲了一点，然后当时也没怎么做题，现在又重新拿出来研究，先敲出来了一个区间和的模板放在这里，再慢慢深入。
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 1e5;
int a[maxn],tree[maxn];
void build(int p,int l,int r)///p线段树上当前节点编号l当前结点区间的左界r右界
{
if(l == r)
{
tree[p] = a[l];
return;
}
int mid = (l + r) / 2;
build(p * 2,l,mid);
build(p * 2 + 1,mid + 1,r);
tree[p] = tree[p * 2] + tree[p * 2 + 1];
}
void change(int p,int l,int r,int x,int num)
{
/*p当前节点编号
l当前节点区间的左界r是右界
x表示需要修改的节点编号
num表示对x增加的值*/
if(l == r)
{
tree[p] += num;
return;
}
int mid = (l + r) / 2;
if(x <= mid)
change(p * 2,l,mid,x,num);
else
change(p * 2 + 1,mid + 1,r,x,num);
tree[p] = tree[p * 2] + tree[p * 2 + 1];
}
int find(int p,int l,int r,int x,int y)
{
/*在plr这棵子树里查询x到y的区间和*/
if(x <= l && r <= y)
return tree[p];
int mid = (l + r) / 2;
if(y <= mid)
return find(p * 2,l,mid,x,y);
if(x > mid)
return find(p * 2 + 1,mid + 1,r,x,y);
return find(p * 2,l,mid,x,mid) + find(p * 2 + 1,mid + 1,r,mid + 1,y);
}
int main()
{
int n;
scanf("%d",&n);
for(int i = 1;i <= n; i++)
scanf("%d",&a[i]);
build(1,1,n); //建树
int p,q;
scanf("%d %d",&p,&q); //查询p到q的区间和
int sum = find(1,1,n,p,q);
printf("%d\n",sum);
int x,num;
scanf("%d %d",&x,&num); //第x个节点加上num
change(1,1,n,x,num);
scanf("%d %d",&p,&q);
sum = find(1,1,n,p,q);
printf("%d\n",sum);
return 0;
}
