树状数组 心已赠人 2022-05-16 05:17 284阅读 0赞 树状数组单点修改,单点查询 洛谷oj :[点我][Link 1] 模板: #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=500000+5; int n,q; int a[N],tree[N]; int lowbit(int x){ return x&(-x); } void update(int x,int val){ while(x<=n){ tree[x]+=val; x+=lowbit(x); } } int query(int x){ int sum=0; while(x>0){ sum+=tree[x]; x-=lowbit(x); } return sum; } int main(){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); update(i,a[i]); } while(q--){ int l,r; int flag; scanf("%d%d%d",&flag,&l,&r); if(flag==1){ update(l,r); } else{ printf("%d\n",query(r)-query(l-1)); } } } 树状数组区间修改,单点查询 洛谷oj:[点我][Link 2] 原来的数值存在a\[\]里面,tree\[i\]=a\[i\]-a\[i-1\]; 求a\[i\]时,a\[i\]=a\[i-1\]+tree\[i\]=a\[i-2\]+tree\[i\]+tree\[i-1\]=…=tree\[1\]+tree\[2\]+…tree\[i\]; #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=500000+5; int n,q; int a[N],tree[N]; int lowbit(int x){ return x&(-x); } void update(int x,int val){ while(x<=n){ tree[x]+=val; x+=lowbit(x); } } int query(int x){ int sum=0; while(x>0){ sum+=tree[x]; x-=lowbit(x); } return sum; } int main(){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); update(i,a[i]-a[i-1]); } while(q--){ int l,r,k; int flag; scanf("%d",&flag); if(flag==1){ scanf("%d%d%d",&l,&r,&k); update(l,k); update(r+1,-k); } else{ int x; scanf("%d",&x); printf("%d\n",query(x)); } } } [Link 1]: https://www.luogu.org/problemnew/show/P3374 [Link 2]: https://www.luogu.org/problemnew/show/P3368
相关 树状数组 详细介绍:[https://www.cnblogs.com/xenny/p/9739600.html][https_www.cnblogs.com_xenny_p_973960 我不是女神ヾ/ 2023年08月17日 16:26/ 0 赞/ 121 阅读
相关 树状数组 目录: 1. 概念 2. 应用 3. 充分性 4. 建立树状数组 5. 典题分析 一.概念 数组来模拟树形结构。那么、为什么不直接建树?没必要,因为树 秒速五厘米/ 2023年02月25日 11:29/ 0 赞/ 22 阅读
相关 树状数组 1、概述 树状数组(binary indexed tree),是一种设计新颖的数组结构,它能够高效地获取数组中连续n个数的和。概括说,树状数组通常用于解决以下问题:数组\{a 朱雀/ 2022年08月10日 10:53/ 0 赞/ 254 阅读
相关 树状数组 树状数组 树状数组:用线性数据结构的方法解决动态统计子树权和的问题。 类似于线段树,将区间分成小段,方便计算权和。 举个栗子,将a数组构造成树状数组c。 如果a 忘是亡心i/ 2022年07月26日 08:44/ 0 赞/ 244 阅读
相关 详解--树状数组 写下这个标题,其实心里还是没底的,与其说是写博帖,不如说是做总结。第一个接触树状数组还是两年前,用什么语言来形容当时的感觉呢?……太神奇了!真的,无法表达出那种感觉 淡淡的烟草味﹌/ 2022年06月10日 03:24/ 0 赞/ 223 阅读
相关 树状数组初探 前言 在前一篇文章:[线段树初探][Link 1] 中我们看了一下线段树的基本思想并且知道了线段树擅长于解决区间问题。其实对于某些区间问题,我们不仅可以用线段树解决,还可 古城微笑少年丶/ 2022年05月30日 03:22/ 0 赞/ 192 阅读
相关 树状数组 树状数组单点修改,单点查询 洛谷oj :[点我][Link 1] 模板: include<iostream> include<cstdio> 心已赠人/ 2022年05月16日 05:17/ 0 赞/ 285 阅读
相关 树状数组实现 树状数组能够完成如下操作: 给一个序列a0-an 计算前i项和 对某个值加x 时间o(logn) 注意:有人觉得前缀和就行了,但是你还要维护啊,改变某个值,一个一个改 叁歲伎倆/ 2022年05月12日 02:44/ 0 赞/ 180 阅读
相关 树状数组板子 树状数组 重点是在树状的数组 大家都知道二叉树吧 叶子结点代表A数组A\[1\]~A\[8\] ![786945-20161206222443741-120171603 r囧r小猫/ 2022年03月15日 15:22/ 0 赞/ 296 阅读
相关 树状数组模板 //树状数组 struct Bit { vector<int> a; int sz; void ini ゞ 浴缸里的玫瑰/ 2021年09月19日 05:46/ 0 赞/ 362 阅读
还没有评论,来说两句吧...