线段树模板(1)
模板 线段
2023-09-11 14:15:53 时间
题解:记得开long long,没啥。
区间更新那一块的递归调用,不断下放,刚开始挺难理解的,也还好。
啊啊,松懈了好多,都怪自己被一部好看的小说引诱了……明天陪发小再玩一趟,赶紧回到正轨上,抓紧学习算法,不能玩物丧志!!!!
人要堕落是很容易的!!况且我想做到的事情还很多呢
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int a[maxn],n,m;
struct node
{
int val,lazy;
}sg[maxn<<2];
void pushup(int rt)
{
sg[rt].val=sg[rt<<1].val+sg[rt<<1|1].val;
}
void build(int l,int r,int rt)
{
if(l==r)
{
sg[rt].val=a[l];return ;
}
sg[rt].lazy=0;
int m=(l+r)/2;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
pushup(rt);
}
void pushdown(int rt,int ln,int rn)
{
if(sg[rt].lazy)
{
sg[rt<<1].lazy+=sg[rt].lazy;
sg[rt<<1|1].lazy+=sg[rt].lazy;
sg[rt<<1].val+=sg[rt].lazy*ln;
sg[rt<<1|1].val+=sg[rt].lazy*rn;
sg[rt].lazy=0;
}
}
void update(int L,int R,int C,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
sg[rt].val+=C*(r-l+1);
sg[rt].lazy+=C;
return;
}
int m=(l+r)>>1;
pushdown(rt,m-l+1,r-m);
if(L<=m) update(L,R,C,l,m,rt<<1);
if(R>m) update(L,R,C,m+1,r,rt<<1|1);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
return sg[rt].val;
if(L>r||R<l)
return 0;
int m=(l+r)/2;
pushdown(rt,m-l+1,r-m);
return query(L,R,l,m,rt<<1)+query(L,R,m+1,r,rt<<1|1);
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
build(1,n,1);
while(m--)
{
//memset()
int g;scanf("%lld",&g);
if(g==1)
{
int x,y,k;scanf("%lld%lld%lld",&x,&y,&k);
update(x,y,k,1,n,1);
}
else if(g==2)
{
int x,y;scanf("%lld%lld",&x,&y);
cout<<query(x,y,1,n,1)<<endl;
}
}
return 0;
}
相关文章
- 设计模式-模板方法模式
- 性能测试方案(计划)模板
- 【洛谷3834】 【模板】可持久化线段树 (主席树)
- Flask框架中Jinja2模板过滤器
- Idea:通过Live Template自定义模板(类注释、方法注释)
- 11Vue - 模板语法(插值-属性)
- python使用模板手记
- 基于 Bootstrap 5 的博客和杂志主题 HTML 网站模板
- Web网站模板-响应式企业产品介绍模板(HTML+CSS+JavaScript)
- 浅析JSX模板组件使用
- EasyExcel根据模板填充(多sheet页封装工具方法)
- 洛谷 P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
- 洛谷 P3811 【模板】乘法逆元
- 注释模板
- 【JVM】模板解释器--字节码的resolve过程
- Python+Django+SAE系列教程10-----Django模板
- 不错的后台模板
- 函数模板概念