rt，bdfs无果

Sqrt-tree查询区间最大值模板，问题在如何优化记录分块区间最大值 $pre$ 数组

$pre$ 实际使用的空间应该只有 $O(nloglogn)$，但是不知道怎么改。。。

#include <bits/stdc++.h>
#define int long long
#define M 10
#define SIZE 100005
using namespace std;
int a[SIZE*2],tot,n,m,N=1,l,r,lg[SIZE*2];
struct sqrt_tree {
    int fro[M][SIZE*2]={},bak[M][SIZE*2]={},pos[M][SIZE*2]={},n,m,pre[M][505][505]={},len[M]={},maxn[M][505]={},siz[M]={},to[105]={};
	void build(int l,int r,int dep){
//		cout<<l<<" "<<r<<" "<<dep<<endl;
		len[dep]=(r-l+1)/siz[dep];
		int lblock=(l-1)/siz[dep]+1;
		int rblock=lblock+len[dep]-1;
		for(int i=lblock;i<=rblock;i++){
			int fl=(i-1)*siz[dep]+1,fr=i*siz[dep];
//			cout<<fl<<" "<<fr<<" "<<dep<<" "<<i<<endl;
			for(int j=fl;j<=fr;j++) pos[dep][j]=i;
			fro[dep][fl]=a[fl],bak[dep][fr]=a[fr];
			for(int j=fl+1;j<=fr;j++) fro[dep][j]=max(fro[dep][j-1],a[j]);
			for(int j=fr-1;j>=fl;j--) bak[dep][j]=max(bak[dep][j+1],a[j]);
			maxn[dep][i]=fro[dep][fr];
			if(fr-fl>1) build(fl,fr,dep+1);
		}
		for(int i=lblock;i<=rblock;i++){
			pre[dep][i][i]=maxn[dep][i];
			for(int j=i+1;j<=rblock;j++){
				pre[dep][i][j]=max(pre[dep][i][j-1],maxn[dep][j]);
			}
		}
	}
	void init(){
		memset(pre,0xcf,sizeof(pre));
		int len=N,cnt=0,k=N,tot=0,d;
		while(k>1) k/=2,cnt++;
		d=cnt;
		while(cnt>1){
			to[cnt]=tot+1;
//			cout<<cnt<<" "<<tot+1<<endl;
			cnt=(cnt+1)/2;
			siz[++tot]=pow(2,cnt);
		}
		to[1]=tot+1;
		for(int i=d;i>=2;i--){
			if(!to[i]) to[i]=to[i+1];
		} 
	}
    int ask(int l,int r){
        if(l==r) return a[l];
        if(r==l+1) return max(a[l],a[r]);
        int dep=to[lg[(l-1)^(r-1)]];
//        cout<<dep<<endl;
        int lx=pos[dep][l],rx=pos[dep][r];
        return max(max(pre[dep][lx+1][rx-1],fro[dep][r]),bak[dep][l]);
    }
} st;
signed main(){
    for(int i=1;i<=400000;i++) lg[i]=lg[i/2]+1; 
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    while(N<n) N*=2;
    st.init();
    st.build(1,N,1);
    for(int i=1;i<=m;i++){
    	scanf("%lld%lld",&l,&r);
    	printf("%lld\n",st.ask(l,r));
	}
}