497
算法训练-线段树
WIKIOI-1080 线段树练习
题目描述 Description
一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；
修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000，,提问和修改的总数
m<10000条。
输入描述 Input Description
输入文件第一行为一个整数N，接下来是n行n个整数，表示格子中原来的整数。接下一个正整数m，再接下来有m行，表示m个询问，第一个整数
表示询问代号，询问代号1表示增加，后面的两个数x和A表示给位置X上的数值增加A，询问代号2表示区间求和，后面两个整数表示a和b，表示
要求[a,b]之间的区间和。
输出描述 Output Description
共m行，每个整数
样例输入 Sample Input
6
4 5 6 2 1 3
4
1 3 5
2 1 4
1 1 9
2 2 6
样例输出 Sample Output
22
22
数据范围及提示 Data Size & Hint
1≤N≤100000， m≤10000 。
本题的目的是训练线段树的构造
AC代码：
#include<stdio.h>
#include<string.h>
struct node//构造线段树需要的结构体
{
int l,r;
int sum;
}a[400010];//线段树需要开2*N以上的空间，此处最容易出错！！
void Bulid(int n,int l,int r)//创建一颗范围为[l,r]的线段树
{
a[n].l=l;//左边界赋值
a[n].r=r;//右边界赋值
a[n].sum=0;//总和初始化
if(l==r)//如果左右孩子相等,创建结束
return;
Bulid(2*n,l,(l+r)/2);//创建左孩子
Bulid(2*n+1,(l+r)/2+1,r);//创建右孩子
}
void Insert(int n,int v,int num)//向线段树插入位置为v的权值num
{
a[n].sum+=num;//更新总和
if(a[n].l==a[n].r)//若左右边界相等，结束更新
return;
if(v<=(a[n].l+a[n].r)/2)//位置小于中间值，往左子树插入，反之去右子树
Insert(n*2,v,num);
else
Insert(n*2+1,v,num);
}
void Change(int n,int v,int num)//改变线段树中位置为v的权值（加上num）
{
if(v==a[n].l&&v==a[n].r)//左右子树相同，执行更新
{
a[n].sum+=num;
return;
}
else
if(v<=(a[n].l+a[n].r)/2)//位置小于中间值，往左子树更新，反之去右子树
Change(n*2,v,num);
else
Change(n*2+1,v,num);
a[n].sum=a[n*2].sum+a[n*2+1].sum;//由于上面的递归已经修改了权值，更新总值
}
int Sum(int n,int l,int r)//计算位置范围在l、r内数权值的总和
{
if(l==a[n].l&&r==a[n].r)//边界等于左右子树，输出本位置的权值和
return a[n].sum;
if(r<=(a[n].l+a[n].r)/2)//右边界小于中间值，往左子树寻找总和
return Sum(n*2,l,r);
else
if(l>(a[n].l+a[n].r)/2)//左边界大于中间值，往右子树寻找总和
return Sum(n*2+1,l,r);
else//不满足上面两个条件，i、r则在 a[n].l与a[n].r中间，那么分别求和
return Sum(n*2,l,(a[n].l+a[n].r)/2)+Sum(n*2+1,(a[n].l+a[n].r)/2+1,r);
}
int main()
{
int i,j,n,m,Q,L,R;
scanf("%d",&n);
Bulid(1,1,n);
for(i=1;i<=n;i++)
{
scanf("%d",&m);
Insert(1,i,m);
}
scanf("%d",&m);
while(m--)
{
scanf("%d %d %d",&Q,&L,&R);
if(Q==1)
{
Change(1,L,R);
}
else if(Q==2)
{
printf("%d\n",Sum(1,L,R));
}
}
return 0;
}
本代码为原创，转载请注明出处！
最后更新：2017-04-03 12:55:38