线段树(segment tree),顾名思义, 是用来存放给定区间(segment, or interval)内对应信息的一种数据结构。与树状数组(binary indexed tree)相似,线段树也用来处理数组相应的区间查询(range query)和元素更新(update)操作。与树状数组不同的是,线段树不止可以适用于区间求和的查询,也可以进行区间最大值,区间最小值(Range Minimum/Maximum Query problem)或者区间异或值的查询。
对应于树状数组,线段树进行更新(update)的操作为O(logn),进行区间查询(range query)的操作也为O(logn)。
求取数组中最大连续子序列和,例如给定数组为A={1, 3, -2, 4, -5}, 则最大连续子序列和为
$math_inline$6$math_inline$
,即
$math_inline$1+3+(-2)+4=6$math_inline$
。
方法一共有三种,复杂度分别为
$math_inline$O(N^2)$math_inline$
、
$math_inline$O(NlgN)$math_inline$
、
$math_inline$O(N)$math_inline$
每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的质因数。如果一个质数是某个数的因数,那么就说这个质数是这个数的质因数。而这个因数一定是一个质数。
把一个合数用质因数相乘的形式表示出来,叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。
质数: 质数(prime number)又称素数,有无限个。
质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。
合数: 合数指自然数中除了能被1和本身整除外,还能被其他数(0除外)整除的数。与之相对的是质数,而1既不属于质数也不属于合数。最小的合数是4。其中,完全数与相亲数是以它为基础的。
首先声明,本博文部分内容仅仅适用于ACM竞赛,并不适用于NOIP与OI竞赛,违规使用可能会遭竞赛处理,请慎重使用!遭遇任何情况都与本人无关哈=7=
我也不想搞得那么严肃的,但真的有些函数在NOIP与OI竞赛中有相关规定不能使用,详细我也不知道各位要了解请自行去找比赛要求咯,当然在ACM竞赛中,没有限制函数,所以所有内容都适用于ACM竞赛。
那么什么是卡常数呢,简单来说就是你和某神犇算法思路一样,结果他的AC了,你的TLE,复杂来说就是程序被卡常数,一般指程序虽然渐进复杂度可以接受,但是由于实现/算法本身的时间常数因子较大,使得无法在OI/ACM等算法竞赛规定的时限内运行结束。
下面就是介绍各种各样的非(花)常(里)实(胡)用(哨)的优化方法的,若本文某些地方有错误或不明确的地方还请指出。=7=