ordinarv

分类

任务(1) 技能树(5)

/ 注册

全部文章（共6篇）

二分

二分 STL(Standard ) lower_bound() 返回第一个大于等于target的位置 upper_bound() 返回第一个大于target的位置 lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到...

2020-09-20

0 456

BIT Interval MAX

首先，a[]数组仍然是保存原始数据。c[i]将会保存从a[1]到a[i]的最值。单点修改时间复杂度log2(n)^2，区间查询时间复杂度log2(n) 1。单点更新：直接更新a[i]，然后再更新h[i]。若h[i]的值有可能改变的，则表示区间一定包含i结点。那么就两层lowbit更新所有...

BIT

2019-08-16

0 603

树状数组总结

目前遇到树状数组的应用有维护区间和(单点修改、区间修改查询) 任意区间最大值求区间第k大(比主席树占用内存小，湘潭某题)

2019-08-16

0 520

线段树

入门题 HDU 3974 Assign the task（简单线段树） HDU 1394 Minimum Inversion Number（求逆序数，线段树或者树状数组） ZOJ 1610 Count the Colors（线段树） POJ2777（区间染色）区间第K大(二分) 矩形面积并推...

2019-08-08

0 605

常用STL函数

lower_bound(l,r,tar) 返回区间内第一个大于等于tar的数位置upper_bound(l,r,tar) 返回区间内第一个大于tar的数位置 lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。在从小到大的排序数组中，lo...

2019-08-07

0 602

树状数组讲课

前言首先来看一个问题：给定a数组单点修改，询问区间和。显然我们有两种思路1.不维护任何东西，直接用a数组 O(1)修改 O(n)求和2.维护a的前缀和，O(n)修改 O(1)求和可是这两种方法都太极端了，我们想均衡一下这两种算法。观察可知前缀和O(n)修改是因为sum[i]维护的是[1...

2019-07-26

0 632