非递归线段树模板

#include <bits/stdc++.h>
using namespace std;

const int M=200010;

int m,p;

int tree[M<<2];
int n,N=1;

void build(){
    //scanf("%d", &n);
    for(;N<=n+1;N<<=1);
    //for(int i=N+1;i<=N+n;i++) scanf("%d", tree+i);
    for(int i=N-1;i>=1;i--) tree[i]=tree[i<<1]+tree[i<<1|1];
}

void modify(int x,int k){
    for(x+=N;x;x>>=1) 
        tree[x]=max(tree[x],k);
}

int query(int s,int r){
    int res=0;
    for(s=N+s-1,r=N+r+1;s^r^1;s>>=1,r>>=1){
        if(~s&1) res=max(res,tree[s^1]);
        if(r&1) res=max(res,tree[r^1]);
    }
    return res;
}

int main(){
    int u=0,last=0;
    scanf("%d%d",&m,&p);
    n=m;
    build();
    int x;
    char op[2];

    while(m--){
        scanf("%s%d",op,&x);
        if(*op=='Q'){
            last=query(u-x+1,u);
            printf("%d\n",last);
        }
        else{
            modify(u+1,(last+x)%p);
            u++;
        }
    }
    return 0;
}