生之、如舟

树状数组

动态规划(8) 博弈论(1) 图论(7) 基本算法(29) 并查集(17) 思维(3) 数学(14) 数据结构(5) 数论(18) 最短路(4) 枚举(1) 树论(4) 模板(7) 比赛(15) 算法总结(3) 线段树(11) 蓝桥杯(1) 贪心(1)

/ 注册

全部文章 / 树状数组（共12篇）

Different GCD Subarray Query HDU - 5869 【离线处理】【gcd】【树状数组】来自专栏

Different GCD Subarray Query HDU - 5869 解法以一个数字结尾的所有连续段gcd，不会超过log个，想象一下一个gcd的唯一分解，每次要产生新的gcd，肯定是从老的gcd去掉一些质因子，也就是说至少会去掉>=2的数，gcd至少变成1/2，是呈指数型减少...

树状数组

2020-11-20

0 724

POJ - 3321 Apple Tree 【树上树状数组】【DFS序】来自专栏

POJ - 3321 Apple Tree 题目链接：https://vjudge.net/problem/POJ-3321#author=mfdy 题目卡卡屋前有一株苹果树，每年秋天，树上长了满苹果。卡卡很喜欢苹果。树上有N个节点，卡卡给他们编号1到N，根的编号永远是1.每个节点上最多结一个苹果...

树状数组

2020-04-19

0 806

POJ - 2155 Matrix 【树状数组】【二维区间修改单点查询】来自专栏

POJ - 2155 Matrix 题目链接：https://vjudge.net/problem/POJ-2155#author=happypeople 题目给定 n* n 矩阵A，其元素为0或1. A [i][j] 表示第i行和第j列中的数字。最初全为0. 我们有两个操作: 1. C x1 y...

树状数组

2020-04-18

0 795

POJ - 2481 Cows 【树状数组】【排序】来自专栏

POJ - 2481 Cows 题目链接：https://vjudge.net/problem/POJ-2481 题目大意在x轴上有很多的线段，问每一个线段是多少个线段的真子集。思路我们可以考虑通过排序，让线段的左端点是从左到右的关系排列，每遍历到一个线段的时候，就看之前有多少个右端点是在[r...

树状数组

2020-04-18

0 848

POJ - 2352 Stars 【树状数组】来自专栏

POJ - 2352 Stars 思路考虑到是从左往右，从下往上给点的，所以可以遍历这个顺序把点插入到树状数组中，每次插入前，看当前树状数组中有多少个x是小于此时的X的，就算是这个点的level了。代码模板大于代码系列 #include <iostream> #include &l...

树状数组

2020-04-17

0 583

POJ-2299 Ultra-QuickSort 【权值树状数组】【思维】来自专栏

Ultra-QuickSort 题目链接：https://vjudge.net/problem/POJ-2299 思路其实我们在学冒泡排序的时候，就可以发现有些相邻交换是不必要的。好的交换应该是使得数值更加的靠近他的真正位置。好的排序过程如图所示：这样每次新添加一个数，就看他之前有多少个比他大的数...

树状数组

2020-04-17

0 768

AcWing 243. 一个简单的整数问题2 【模板题】【树状数组】【区间修改区间查询】来自专栏

243. 一个简单的整数问题2 题目链接：https://www.acwing.com/problem/content/description/244/ 思路维护了两个差分树状数组，差分树状数组的区间查询其实就是求一个近似半矩阵的区域，通过近似补矩阵的方法，就可以通过两个比较好算的两个求和，让两个...

树状数组

2020-04-16

0 687

AcWing 242. 一个简单的整数问题【树状数组】【区间修改单点查询】来自专栏

AcWing 242. 一个简单的整数问题题目链接：https://www.acwing.com/problem/content/248/ 思路把树状数组改成差分数组，每次算差分后的一个数其实就是算前缀和代码 #include<bits/stdc++.h> #define ios ...

树状数组

2020-04-16

0 698

AcWing 241. 楼兰图腾【权值树状数组】【模板题】来自专栏

241. 楼兰图腾题目链接：https://www.acwing.com/problem/content/description/243/ 思路遍历1-n，每次往树状数组的arr[i]位置插入1，表示arr[i]出现过一次。每当遍历到i时，就能通过树状数组查询小于arr[i]的元素个数，和大于a...

树状数组

2020-04-16

0 895

ACWing 244. 谜一样的牛【树状数组】来自专栏

244. 谜一样的牛题目链接：https://www.acwing.com/problem/content/description/245/ 思路计算末尾的牛身高的时候，可以发现就是求他在剩余可选身高中排第几的问题。可以用树状数组算query(r)：前r身高还有多少个。这样对于一头牛说，前面比他...

树状数组

2020-04-15

0 807