python的话只能非递归去写了

代码大家先看下

具体的话大家可以看下这个链接 link

简单说一下

#线段树非递归写法,可以结合上面那个图去理解下
m, p = map(int, input().split())

def build():
    for i in range(m - 1, 0,-1):#从底向上更新,这里的m呢是array的大小哈
        tr[i] = max(tr[i << 1], tr[i << 1 | 1])

def modify(u, v):
    u += m #为什么加m?看下图就明白了,加n就是对应的最后一行的叶子节点
    tr[u] = max(v, tr[u])
    while u > 1:
        tr[u >> 1] = max(tr[u], tr[u ^ 1])
        u >>= 1
def query(l, r):
    res = 0
    l += m; r += m
    while l < r:
        if l & 1: res = max(res, tr[l]); l += 1#如果l是奇数，说明这是一个单独的点，取个max，然后++
        if r & 1: r -= 1; res = max(res, tr[r])#同理
        l >>= 1; r >>= 1
    return res

last = 0
n = 0
tr = [0] * (2 * m + 100)
for i in range(m):
    a, b = input().split()

    b = int(b)
    if a == 'A':
        modify(n, (last + b) % p)
        n += 1
    if a == 'Q':
        last = query(n - b, n)
        print(last)

上面只是简单理解,还是希望大家去看下原链接

递归写法, 会超时,仅供参考

m, p = map(int, input().split())

N = 100000
class node:
    l = r = 0
    mx = 0
    def __init__(self, l, r, mx):
        self.l = l
        self.r = r
        self.mx = mx
tr = [None for i in range(4 * N)]

def pushup(u):#获取区间最大值，更新
    tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx)

def build(u, l, r):
    tr[u] = node(l, r, 0)
    if l == r: return
    mid = l + r >> 1
    build(u << 1, l, mid)
    build(u << 1 | 1, mid + 1, r)

def query(u, l, r):
    if l <= tr[u].l and r >= tr[u].r: return tr[u].mx
    #节点被完全包含，直接返回区间最大值

    mid = tr[u].l + tr[u].r >> 1
    v = 0
    if l <= mid: v = query(u << 1, l, r)
    if r > mid: v = max(v, query(u << 1 | 1, l ,r))#这里大于mid是因为右节点是mid + 1开始的
    return v

def modify(u, x, v):
    if tr[u].l == x and tr[u].r == x: tr[u].mx = v#这个节点最有端点相等并且都是x说明找到了要修改的点
    else:  
        mid = tr[u].l + tr[u].r >> 1
        if x <= mid: modify(u << 1, x, v)
        if x > mid: modify(u << 1 | 1, x, v)
        pushup(u)


last = 0
n = 0
build(1, 1, m)
for i in range(m):
    a, b = input().split()

    b = int(b)
    if a == 'A':
        modify(1, n + 1, (last + b) % p)
        n += 1
    if a == 'Q':
        last = query(1, n - b + 1, n)
        print(last)