Posted on 2009-05-26 12:24
chenweiwei 阅读(1495)
评论(2) 编辑 收藏 引用
A Simple Problem with Integers
Description
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
...............
一道简单的线段树题目，但是因为数据量大（1000000000 ≤ Ai ≤ 1000000000），按照常规的解法必然会超时，这里需要增加一些变量保存区间内的改变量.
结点定义：
这里结点有五个变量，分别是左子树，右子树，区间的初始值。对区间整体的改变值。该区间及子区间改变值
struct node
{
int l; //左子树
int r; //右子树
__int64 value; //区间的初始量
__int64 tsum; //对区间的整体改变量
__int64 adt; //对区间及子区间的改变值
}Node[400040];初始化：
建树的时候，每个结点保存这个结点跟其子树的结点值总和。
int build(int a,int b,int s)
{
Node[s].l=a;
Node[s].r=b;
if(a==b)
{
Node[s].value=v[a];
return 0;
}
else
{
int mid=(a+b)/2;
build(a,mid,s*2);
build(mid+1,b,s*2+1);
Node[s].value=Node[s*2].value+Node[s*2+1].value;
return 0;
}
}
更新：
更新的时候，tsum记录整个区间的改变量。
int Modify(int a,int b,int s)
{
Node[s].tsum+=(b-a+1)*mValue;
if(Node[s].l==a && Node[s].r==b)
{
Node[s].adt+=mValue;
}
else
{
int mid=(Node[s].l+Node[s].r)>>1;
if(b<=mid)
{
Modify(a,b,s*2);
}
else if(a>mid)
{
Modify(a,b,s*2+1);
}
else
{
Modify(a,mid,s*2);
Modify(mid+1,b,s*2+1);
}
// Node[s].value=Node[s*2].value+Node[s*2+1].value;
}
return 0;
}
查询：
__int64 Query(int a,int b,int s)
{
__int64 cost=0;
if(Node[s].l==a && Node[s].r==b)
{
cost += Node[s].value + Node[s].tsum;
}
else
{
cost+=(b-a+1)*Node[s].adt;
int mid=(Node[s].l+Node[s].r)>>1;
if(b<=mid)
{
cost+=Query(a,b,s*2);
}
else if(a>mid)
{
cost+=Query(a,b,s*2+1);
}
else
{
cost+=Query(a,mid,s*2);
cost+=Query(mid+1,b,s*2+1);
}
}
return cost;
}