倍增，字面上翻了一番。 也就是说，在递归期间，如果状态空间较大，常规线性递归不能满足时间和空间复杂性的要求，则只有递归状态空间2的整数次幂位置的值是代表性值。 如果需要其他位置的值，可以使用“任意整数可以表示为几个2的幂项之和”的性质(13=2^3 2^2 2^0)，用之前求出的代表值拼成所需的值。
给出长度为n的数列a，进行数次查询，每次给出整数t求最大的k，满足。算法必须在线()每次给出查询都会得出结果)；
当然，可以先预处理前缀和(A[i] 0)，然后在两分钟内找到这个k。 这个复杂性最坏的情况是o ) n )。 因为如果我们咨询的t太小，最好走了再列举。
可以设计这样的倍频算法：
假设p=1、k=0、sum=0；
2 .比较' a序列中k后p个数之和'与t的关系。 即，在sum s[k p] - s[k]=T的情况下，sum =s[k p] -s[k]，k=p，p*=2； 也就是说，把这个p的个数之和相加，使p的跨度加倍了。 在sum s[k p] - s[k] T的情况下，设为p /=2。
3重复前面的步骤，到p的值为0为止，此时k是答案。
列举a序列下标123456789值123456789S序列136101521283645例，a序列及其前缀和上图。
最初为p=1、k=0、sum=0； 即以k=0为开始端点，p个数之和，S[0]=0；
例如我们的T=13；
初次：S[1] - S[0]=a[1]=1，sum S[1] - S[0]=0 1=1 T； 1个数a[1]
那么，k=p，p*=2； 此时k=1、p=2； sum=1
第二次： S[2 1] - S[1]=a[1] a[2]=5，sum S[2 1] - S[1]=1 5=6 T； 2个数a[1]，a[2]
接着，k =p，p*=2； 此时k=3、p=4； sum=6
第三次3360 s [ 34 ]-s [3]=a [4] a [5] a [6] a [7]=22，sums [3]-s [3]=6，22t； 4个数a[4] ~ a[7]
那么p /=2； 此时k=3、p=2； sum不更新
第四批： S[3 2] - S[3]=a[4] a[5]=9 T，sum=9 6=15 T； 2个数a[4]，a[5]
那么p/=2； 此时k=3、p=1； sum=6
第五届： S[4] - S[3]=a[4]=4，sum=6(4=10t
那么，k=p，p*=2； 此时k=4、p=2； sum=10；
第六届： S[6] - S[4]=11，sum S[6] - S[4]=10 11=22 T
p /=2； sum=10，p=1；
第七届： S[5] - S[4]=5，sum S[5] - S[4]=5 10=15 T；
那么p/=2，p=0； 结束了
k=4；
# include iostream # include cstdio # include cstring # includealgorithmusingnamespacestd； 常数上限=1005； 泰普德夫龙龙LL； int sum[MAX]； int a[MAX]； int main () {int n； cin n； for(intI=1； i=n； I () {cin a[i]； sum[i]=sum[i-1] a[i]； (}int T； int k=0，p=1，s=0； cinT； wile(1) if (p==0) ) {break； (if ) ssum[kp]-sum[k]=t ) {s=sum[k p]-sum[k]； k=p； p*=2； }else{p/=2； }}coutk； 返回0； }