線段樹，區間增減，區間求和。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/2 10:51:34
* File Name: poj3468.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(100007);
struct Node
{
int a,b;
int64 sum,add;
};
int n,Q,r[kMaxn];
Node tree[kMaxn<<2];
void Build(int node,int x,int y)
{
tree[node].a=x;
tree[node].b=y;
tree[node].add=0;
if(x==y)
tree[node].sum=r[x];
else
{
int m(Half(x+y));
Build(L(node),x,m);
Build(R(node),m+1,y);
tree[node].sum=tree[L(node)].sum+tree[R(node)].sum;
}
}
void Update(int node)
{
if(tree[node].add)
{
tree[L(node)].add+=tree[node].add;
tree[R(node)].add+=tree[node].add;
tree[L(node)].sum+=(tree[L(node)].b-tree[L(node)].a+1)*tree[node].add;
tree[R(node)].sum+=(tree[R(node)].b-tree[R(node)].a+1)*tree[node].add;
tree[node].add=0;
}
}
void Add(int node,int x,int y,int delta)
{
if(x<=tree[node].a && tree[node].b<=y)
{
tree[node].add+=delta;
tree[node].sum+=(tree[node].b-tree[node].a+1)*delta;
}
else
{
Update(node);
int m(Half(tree[node].a+tree[node].b));
if(x<=m)
Add(L(node),x,y,delta);
if(y>m)
Add(R(node),x,y,delta);
tree[node].sum=tree[L(node)].sum+tree[R(node)].sum;
}
}
int64 Sum(int node,int x,int y)
{
if(x<=tree[node].a && tree[node].b<=y)
return tree[node].sum;
else
{
Update(node);
int64 re(0);
int m(Half(tree[node].a+tree[node].b));
if(x<=m)
re+=Sum(L(node),x,y);
if(y>m)
re+=Sum(R(node),x,y);
return re;
}
}
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d%d",&n,&Q)==2)
{
for(int i=1;i<=n;i++)
scanf("%d",&r[i]);
Build(1,1,n);
while(Q--)
{
string cmd;
int a,b,c;
cin>>cmd;
if(cmd=="C")
{
scanf("%d%d%d",&a,&b,&c);
Add(1,a,b,c);
}
else
{
scanf("%d%d",&a,&b);
cout<<Sum(1,a,b)<<endl;
}
}
}
return 0;
}
posted on 2011-08-02 11:15
lee1r 閱讀(468)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構