模板_SEG_TREE
2024-10-07 05:43:56
#include<bits/stdc++.h>
#define maxn 500005
#define int long long
using namespace std;
inline int read()
{
char x = getchar();
int lin = , f = ;
while(x < '' || x > '')
{
if(x == '-') f = -;
x = getchar();
}
while(x >= '' && x <= '')
{
lin = (lin << ) + (lin << ) + x - '';
x = getchar();
}
return lin * f;
}
#define PII pair<int,int>
#define fir first
#define sec second
#define ma(a,b) make_pair(a,b)
#define db double
#define inf 123123123
int n,m,v[maxn],x,y,ty,val;
struct tree{
int l,r,add,val;
}tr[maxn];
#define le tr[k].l
#define re tr[k].r
#define upd tr[k].val = tr[k << 1].val + tr[k << 1 | 1].val;
void pbd(int k,int val)
{
tr[k].val = tr[k].val + (re - le + ) * val;
tr[k].add = tr[k].add + val;
}
void pb(int k)
{
if(tr[k].add)
{
pbd(k << ,tr[k].add);
pbd(k << | ,tr[k].add);
tr[k].add = ;
}
}
void update(int l,int r,int k,int val)
{
if(l <= le && re <= r) { pbd(k,val); return; }
pb(k);
int mid = le + re >> ;
if(l <= mid) update(l,r,k << ,val);
if(r > mid) update(l,r,k << | ,val);
upd;
}
int query(int l,int r,int k)
{
if(l <= le && re <= r) return tr[k].val;
pb(k);
int ans = ,mid = le + re >> ;
if(l <= mid) ans = ans + query(l,r,k << );
if(r > mid) ans = ans + query(l,r,k << | );
return ans;
}
void build(int l,int r,int k)
{
le = l; re = r;
if(l == r) { tr[k].val = v[l]; return; }
int mid = l + r >> ;
build(l,mid,k << ); build(mid + ,r,k << | );
upd;
}
signed main(){
n = read(); m = read();
for(int i = ; i <= n; i++) v[i] = read();
build(,n,);
for(int i = ; i <= m; i++)
{
ty = read(); x = read(); y = read();
if(ty == ) { val = read(); update(x,y,,val); }
else printf("%lld\n",query(x,y,));
}
}
最新文章
- 浅谈Linux内存管理机制
- ext 对齐
- Objective-C学习笔记-第三天(1)
- Windows系统中Git的安装配置
- oracle——session
- 设置SQLServer数据库中某些表为只读的多种方法
- 查找 SqlServer死锁
- dede表前缀不定时,查询表#@__archives
- Button控件的点击事件
- redis cluster简介和配置(3)
- 常见类 Object
- MySQL-8.0.11与Navicat Premium安装教程
- [转] AppArmor
- Postgresql ODBC驱动,用sqlserver添加dblink跨库访问postgresql数据库
- CSU 1808 地铁(最短路变形)
- notepad++上搭建gtk+2.0/3.x开发环境
- UITableView中cell点击的绚丽动画效果
- Gym 101243E	Cupcakes
- JavaScript设计模式-21.命令模式
- sublime3配置java开发环境
热门文章
- HDU 1074 Doing Homework (状压DP)
- HDU 4585 Shaolin (STL map)
- Android Studio 如何获取 text文本内容
- IIS web服务器与ASP.NET
- 浅谈Javascript数据属性与访问器属性
- Zookeeper 和Eureka比较
- 洛谷 P2868 [USACO07DEC]观光奶牛Sightseeing Cows 题解
- P1550打井
- <;<;C++ Primer>;>; 第一章 开始 术语表
- python requests的content和text方法的区别【转】