APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
树状数组
OI

#NOIP提高组#模板整理

高精度运算 高精度加法: int main() { scanf("%s%s",&a1,&b1); if(a1[0] == '0' && b1[0] == '0') { cout << "0"; return 0; } for(int i = 0;i < strlen(a1);++i) a[strlen(a1) - i - 1] = a1[i] - '0'; for(i…

2018年11月4日 1条评论 1562点热度 2人点赞 神楽坂 みずき 阅读全文
OI

#C/C++#数据结构:树状数组/线段树/并查集/树链剖分

数据结构 树状数组,堆 线段树  单点,区间 动态开结点 并查集 加了路径压缩之后不能随便撤销 使用启发式合并复杂度是 O(n log n),按秩合并是 O(nα(n))。 平衡树 treap 比较好写 splay 比较难写, noip 也不会考这么高级的东西 只能说 (开了 O2 的)set 秒杀一切 dfs 序与树链剖分 非传统方法 点事件 分块 cdq 分治 树状数组 具体思想就是要维护一个序列 a 的前缀和,我们可以维护一个辅助序列 s,使得 si = ∑j2(i-lowbit(i);i] aj,然后我们发…

2018年10月3日 0条评论 1303点热度 0人点赞 神楽坂 みずき 阅读全文
OI

#C/C++#数据结构:一维树状数组/二维树状数组模板

模板 #define lowbit(x) x & -x //1D void add(int x,int t) { while(x <= n) { v[x] += t; x += lowbit(x); } } int query(int x) { int res = 0; while(x) { res += v[x]; x -= lowbit(x); } return res; } //2D n * m void add(int x,int y,int t) { while(x <= n) { f…

2018年10月2日 0条评论 1253点热度 0人点赞 神楽坂 みずき 阅读全文
OI

#C/C++#树状数组模板

问题模型 现在有一个这样的问题:有一个数组a,,现在给你w次修改,q次查询,修改的话是修改数组中某一个元素的值;查询的话是查询数组中任意一个区间的和。 这个问题很常见,首先分析下朴素做法的时间复杂度,修改是O(1)的时间复杂度,而查询的话是O(n)的复杂度,总体时间复杂度为O(qn) 可能你会想到前缀和来优化这个查询,我们也来分析下,查询的话是O(1)的复杂度,而修改的时候修改一个点,那么在之后的所有前缀和都要更新,所以修改的时间复杂度是O(n),总体时间复杂度还是O(qn)。 可以发现,两种做法中,要么查询是O(…

2018年6月29日 0条评论 1774点热度 0人点赞 神楽坂 みずき 阅读全文

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
#模板分享#我永远喜欢加藤惠个人主页HTML模板 #动漫#我的青春恋爱物语果然有问题:OP/ED/角色歌/Flac无损音乐下载 Yandex Money塑料实体万事达借记卡评测 StickerMule1刀全球包邮Unixstickers贴纸评测 站点域名变更通知 C++程序查看运行时间&&空间大小&&程序运行分析
标签聚合
动漫 C/C++ ST 日常 OI 洛谷 C++ HTML
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang