c - 优化线段树的范围最大查询？

Question

所以我再次需要一些帮助。我最近开始在 codechef 上解决中等水平的问题，因此我得到了很多 TLE。

所以基本上问题是找到问题中给出的多个最大范围查询的总和。给出了初始范围，并通过问题中给出的公式计算下一个值。

我使用线段树来解决这个问题，但是我不断地得到一些子任务的TLE。请帮我优化这段代码。

问题链接-https://www.codechef.com/problems/FRMQ

//solved using segment tree
#include <stdio.h>
#define gc getchar_unlocked
inline int read_int()  //fast input function 
{
    char c = gc();
    while(c<'0' || c>'9') 
        c = gc();
    int ret = 0;
    while(c>='0' && c<='9') 
    {
        ret = 10 * ret + c - '0';
        c = gc();
    }
    return ret;
}
int min(int a,int b)
{
    return (a<b?a:b);
}
int max(int a,int b)
{
    return (a>b?a:b);
}
void construct(int a[],int tree[],int low,int high,int pos)  //constructs 
{                                          //the segment tree by recursion
    if(low==high)
    {
        tree[pos]=a[low];
        return;
    }
    int mid=(low+high)>>1;
    construct(a,tree,low,mid,(pos<<1)+1);
    construct(a,tree,mid+1,high,(pos<<1)+2);
    tree[pos]=max(tree[(pos<<1)+1],tree[(pos<<1)+2]);
}
int query(int tree[],int qlow,int qhigh,int low,int high,int pos)
{   //function finds the maximum value using the 3 cases
    if(qlow<=low && qhigh>=high)
        return tree[pos];            //total overlap
    if(qlow>high || qhigh<low)
        return -1;                   //no overlap
    int mid=(low+high)>>1;           //else partial overlap
    return max(query(tree,qlow,qhigh,low,mid,(pos<<1)+1),query(tree,qlow,qhigh,mid+1,high,(pos<<1)+2));
}
int main()
{
    int n,m,i,temp,x,y,ql,qh;
    long long int sum;
    n=read_int();
    int a[n];
    for(i=0;i<n;i++)
        a[i]=read_int();
    i=1;
    while(temp<n)       //find size of tree
    {
        temp=1<<i;
        i++;
    }
    int size=(temp<<1)-1;
    int tree[size];
    construct(a,tree,0,n-1,0);
    m=read_int();
    x=read_int();
    y=read_int();
    sum=0;
    for(i=0;i<m;i++)
    {
        ql=min(x,y);
        qh=max(x,y);
        sum+=query(tree,ql,qh,0,n-1,0);
        x=(x+7)%(n-1);     //formula to generate the range of query
        y=(y+11)%n;
    }
    printf("%lld",sum);
    return 0;
}

Answer 1

几点说明:

1. 很高兴您使用快速 IO 例程。
2. 确保您不使用模运算，因为它非常慢。要计算余数，只需从数字中减去 N，直到它小于 N。这样会更快。
3. 您的算法需要 O((M+N) * log N) 时间，这不是最优的。对于静态RMQ问题，使用sparse table更好也更简单。 。它需要 O(N log N) 空间和 O(M + N log N) 时间。