RMQ,树状数组模板

RMQ

关于RMQ介绍:RMQ (Range Minimum/Maximum Query)算法

RMQ用于先预处理一下,一段数列,然后可以很快的求出区间最大最小值,他在O(nlog(n))的时间预处理,在O(1)的时间查询.

首先数预处理:

void RMQ(int num) //预处理->O(nlogn)  
{  
    for(int j = 1; j < 20; ++j)  
        for(int i = 1; i <= num; ++i)  
            if(i + (1 << j) - 1 <= num)  
            {  
                maxsum[i][j] = max(maxsum[i][j - 1], maxsum[i + (1 << (j - 1))][j - 1]);  
                minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]);  
            }  
}

查询的时候,设要查询的区间是[a,b]:

int k=(int)(log(b-a+1.0)/log(2.0));
int maxnum=max(maxx[a][k],maxx[b-(1<<k)+1][k]);
int minnum=min(minn[a][k],minn[b-(1<<k)+1][k]);

树状数组

树状数组用来快速的求,一个数列的前n项和

lowbit(x),这是一个自定义的函数,函数名是约定成俗的,作用就是返回x的二进制表示中最后一位1的权值 :

int lowbit(int x)//位运算,利用计算机补码特性  
{  
    return x&-x;  
}

求前n项和:

int sum(int n)  
{    
    int sum=0;    
    while(n>0)    
    {    
        sum+=c[n];    
        n=n-lowbit(n);  
    }    
    return sum;    
}

更新:

void add(int i,int k)  
{  
    while(i<=N)  
    {  
        c[i]+=k;  
        i+=lowbit(i);  
    }  
}

 

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注