poj_3468,线段树成段更新
2024-08-31 13:55:22
参考自http://www.notonlysuccess.com/index.php/segment-tree-complete/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int maxn=111111;
long long sum[maxn<<2];
long long col[maxn<<2];
void pushUp(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushDown(int rt,int m)
{
if(col[rt])
{
col[rt<<1]+=col[rt];
col[rt<<1|1]+=col[rt];
sum[rt<<1]+=col[rt]*(m-(m>>1));
sum[rt<<1|1]+=col[rt]*(m>>1);
col[rt]=0;
}
}
void build(int l,int r,int rt)
{
col[rt]=0;
if(r==l)
{
scanf("%lld",&sum[rt]);
return ;
}
int m=(r+l)>>1;
build(lson);
build(rson);
pushUp(rt);
}
void update(int L,int R,int d,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
sum[rt]+=d*(r-l+1);
col[rt]+=d;
return;
}
pushDown(rt,r-l+1);
int m=(l+r)>>1;
if(L<=m) update(L,R,d,lson);
if(m<R) update(L,R,d,rson);
pushUp(rt);
}
long long query(int L,int R,int l,int r,int rt)
{
long long ret=0;
if(L<=l&&r<=R)
{
return sum[rt];
}
pushDown(rt,r-l+1);
int m=(r+l)>>1;
if(L<=m) ret+=query(L,R,lson);
if(m<R) ret+=query(L,R,rson);
return ret;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
build(1,n,1);
char c;
long long a,b,d;
for(int i=0;i<m;i++)
{
getchar();
scanf("%c%lld%lld",&c,&a,&b);
if(c=='Q')
printf("%lld\n",query(a,b,1,n,1));
else
{
scanf("%lld",&d);
update(a,b,d,1,n,1);
}
}
}
return 0;
}
最新文章
- nginx负载均衡集群
- 针对Asp.net MVC SEO的几点建议
- 如何判断两个String是否是Anagrams_java实现
- 关于childNodes的length的问题
- 10+优秀“分步引导”jQuery插件(转)
- uva 12549 最大流
- 数学语言和程序语言的对比:面向过程与面向集合&;命题
- Android注解支持(Support Annotations)
- IP 转地址
- WSAEventSelect
- CF卡是什么
- 让Sqlite脱离VC++ Runtime独立执行
- [Q]“获取AutoCAD安装信息时失败...”解决方法
- ASP.NET 运行机制详解
- 如何编写更好的SQL查询:终极指南-第一部分
- SqlBulkCopy效率低下原因分析
- 利用拷贝data目录文件的方式迁移mysql数据库
- iOS xcode9 framework静态库的创建以及xib和图片的使用记录
- 2018-2019 20165232 Exp5 MSF基础应用
- Java 学习札记(二)TomCat安装配置