LibreOJ#132. 树状数组 3 :区间修改,区间查询
2023-04-18 15:51:27 时间
【区间修改,区间查询】
https://loj.ac/p/132
题意
解析
代码
做的时候是按照洛谷线段树1那题做的,范围10^18。但其实会有问题,求和过程中可能会爆longlong。
求一次前缀,实际上就是
这是sum(k)
区间查询 就是求 sum(r) - sum(l)
用两个树状数组,一个实现(D_i) 另一个实现(i-1)*(D_i)
方便无脑,直接搞两个add和sum。其实也可以用传数组的形式。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll tr1[N],tr2[N],n,m;
int lowbit(ll x){
return x & -x;
}
void add1(ll x,ll k){
while(x <= n){
tr1[x] += k;
x = x + lowbit(x);
}
}
void add2(ll x,ll k){
while(x <= n){
tr2[x] += k;
x = x + lowbit(x);
}
}
ll sum1(ll x){
ll ans = 0;
while(x >= 1){
ans += tr1[x];
x = x - lowbit(x);
}
return ans;
}
ll sum2(ll x){
ll ans = 0;
while(x >= 1){
ans += tr2[x];
x = x - lowbit(x);
}
return ans;
}
int main(){
scanf("%lld %lld",&n,&m);
int last = 0;
for(int i=1;i<=n;i++){
ll x;
scanf("%lld",&x);
add1(i,x-last);
add2(i,(x-last)*(i-1));
last = x;
}
while(m--){
ll op,x,y,k;
scanf("%lld %lld %lld",&op,&x,&y);
if(op == 1){
scanf("%lld",&k);
add1(x,k);
add1(y+1,-k);
add2(x,k*(x-1));//维护(i-1)*D[i]
add2(y+1,-k*y);//k*y = k*((y+1)-1)
}else{
//注意 如果范围比较大 y * sum1(y) 会爆longlong
printf("%lld
", y*sum1(y)-(x-1)*sum1(x-1)-(sum2(y)-sum2(x-1)));
}
}
return 0;
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击