当前位置: 首页 > news >正文

树状数组

P3374 【模板】树状数组 1

树状数组的初始长相其实跟 \(st\) 有点像,都是像二进制一样拼接而来,那么原始树状数组中数据其实就是被这一层包含的下一层的数据之和。那么我们借鉴一下老师的图。

https://cdn.luogu.com.cn/upload/image_hosting/t887k6nt.png?x-oss-process=image/resize,m_lfit,h_170,w_225

然后我们其实可以去掉一些空间,因为我们可以发现所有偶数位置上的数据可以通过奇数位求出来。那么偶数位就是可有可无的。简称无用区间。

那么我们定义树状数组 \(c_i\) 表示以 \(i\) 为结尾,长度为 \(2^?\) 的取件答案。是的,就是 ? 号次方。我们可以推导一下。当假设 \(a_i\) 为 原数组,\(c_i\) 为树状数组。

c[1] = a[1];
c[2] = a[1] + a[2];
c[1] = a[3];
c[2] = a[1] + a[2] + a[3] + a[4];

那么我们可知 \(c_i\) 代表的区间长度为 \(i , i + 2^i - 1\)。同时根据以上数据可知每次隔了一个后就立马进行区间合并。然后,我们应该怎么求区间答案呢?

首先我们先了解一下只保留奇数位置的数据时怎么求偶数位,首先当要的只再奇数位是就不用管,直接加。否则我们现在的答案减去奇数位就可以得出偶数位。

那么,我们就可以先加上区间 \([x - lowbit(x) + 1 , x]\) 的和,然后我们进行二进制拆分,知道 \(x <= 0\) 即可。

只与修改的话,我们可以发现如果修改一个数那么其实只有与这个数有关的发生变化。比如你加上 \(k\) 那么你的上司,你上司的上司都加上,一直到老板都加上 \(k\)。那么就一个往上找上司,让后修改答案。

那么其实 \(c_i\)\(c_{i + lowbit(i)}\) 包含的话其实就可以直接建边的。那么此题可解。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int c[1000005];
int a[1000005];
int n,m;
int lowbit(int x){return (x & (-x));
}
int query(int x){int ans = 0;while(x > 0){ans += c[x];x -= lowbit(x);}return ans;
}
void modify(int idx,int val,int k){while(idx <= k){c[idx] += val;idx += lowbit(idx);}
}
void build(){for(int i = 1 ; i <= n ; i ++){modify(i , a[i] , n);}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin >> n >> m;for(int i = 1 ; i <= n ; i ++){cin >> a[i];}build();while(m --){int op,l,r;cin >> op >> l >> r;if(op == 1){modify(l , r , n);}else{cout << query(r) - query(l - 1) << "\n"; }}return 0;
}

P3368 【模板】树状数组 2

这一次我们的修改时区间修改,那么什么算法能解决区间修改呢?差分就是一个好帮手,那么我们就可以对数组做差分。

我们知道修改时差分时左端点加上 \(x\) 右端点加一减去 \(x\) 那么我们的修改就从原来的修改一个点改成做差分后的数组修改左端点和右端点加一即可。

其余不变

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int c[1000005];
int b[1000005];
int a[1000005];
int n,m;
int lowbit(int x){return (x & (-x));
}
int query(int x){int ans = 0;while(x > 0){ans += c[x];x -= lowbit(x);}return ans;
}
void modify(int idx,int val,int k){while(idx <= k){c[idx] += val;idx += lowbit(idx);}
}
void build(){for(int i = 1 ; i <= n ; i ++){modify(i , b[i] , n);}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin >> n >> m; for(int i = 1 ; i <= n ; i ++){cin >> a[i];b[i] = a[i] - a[i - 1];}build();while(m --){int op;int x,y,k;cin >> op;if(op == 1){cin >> x >> y >> k;modify(x , k , n);modify(y + 1, -k , n);}else{cin >> x;cout << query(x) << "\n";}}return 0;
}
http://www.hskmm.com/?act=detail&tid=34877

相关文章:

  • 如何管控文件外发安全,确保企业数据不被泄露
  • 打通CI/CD最后一公里:制品库如何成为高效流水线的核心枢纽
  • 2025年10月高端奢侈家电品牌推荐排行榜及深度对比分析
  • 嵌入式调式方案:
  • 2025年10月高端奢侈家电品牌推荐排行榜对比与深度评测分析
  • 2025年GEO品牌推荐排行榜前十强权威发布
  • 2025年GEO品牌推荐榜与排行榜Top10:权威解析与行业洞察
  • 2025年10月高端奢侈家电品牌推荐排行榜单对比与评测分析
  • 第五章 linux实战-CMS01
  • 字典树
  • 2025年10月高端奢侈家电品牌推荐排行榜:五大品牌综合对比与选购指南
  • mysql 更新默认时间
  • A. Vasya and Petyas Game
  • Android Studio Archive | Android Studio 归档下载
  • 关系型数据库的基本理论
  • JAVA集合
  • 【最新推荐】分享十大常用又靠谱的文件摆渡系统
  • C语言实现LDPC码译码功能
  • 2025年10月中国试验机厂家推荐:十强榜单对比与性能评测
  • [NOIP 2012 提高组] 开车旅行 的AC代码
  • Voice Chat: Resolving Lag and Stuttering with a Jitter Buffer
  • 2025 年报警器经销商最新推荐榜单:全面剖析海湾、青鸟等品牌服务商优势,为您筛选优质可靠合作伙伴燃气 / 太阳能 / 交通道路报警器推荐
  • 结构体
  • 专栏导航:《数据中心网络与异构计算:从瓶颈突破到架构革命》 - 实践
  • 扫描线总结
  • 2025年10月抗老面霜推荐:小鸟传领衔五强对比评测榜
  • 基于STM32芯片通过CAN总线控制电机运动
  • 2025 酒店家具厂家最新推荐榜:北木斋领衔五大新锐品牌,品质与创新双优之选全解析
  • 文献阅读笔记格式
  • Stream流