目录

1.1270. 数列区间最大值 - AcWing题库

2.1215. 小朋友排队 - AcWing题库

3.797. 差分 - AcWing题库

4.二维差分

1.1270. 数列区间最大值 - AcWing题库

python日常超时

def pushup(u):
    tree[u][0]=max(tree[u<<1][0],tree[u<<1|1][0])
    return
def build(u,l,r):
    if l==r:
        tree[u]=[w[l],l,r]
    else:
        tree[u]=[0,l,r]
        mid=l+r>>1
        build(u<<1,l,mid)
        build(u<<1|1,mid+1,r)
        pushup(u)
    return

def query(u,l,r):
    if tree[u][1]>=l and tree[u][2]<=r:
        return tree[u][0]
    else:
        maxium=0
        mid=tree[u][1]+tree[u][2]>>1
        if l<=mid:

            maxium=max(maxium,query(u<<1,l,r))
        if r>mid:
            maxium=max(maxium,query(u<<1|1,l,r))
        return maxium

N=10004
n,m=map(int,input().split())
w=[0]+list(map(int,input().split()))
tree=[[]for i in range(4*N)]
build(1,1,n)
for _ in range(m):
    x,y=map(int,input().split())
    print(query(1,x,y))

2.1215. 小朋友排队 - AcWing题库

N=1000005
def lowbit(x):
    return x&-x
def add(x,v):
    i=x
    while i0:
        sums+=tree[i]
        i-=lowbit(i)
    return sums

n=int(input())
a=[0]+list(map(int,input().split()))
a=list(map(lambda x:x+1,a))
tree=[0 for i in range(N+1)]
sums=[0 for i in range(n+1)]
for i in range(1,n+1):
    sums[i]=query(N-1)-query(a[i])
    add(a[i],1)
tree=[0 for i in range(N+1)]
for i in range(n,0,-1):
    sums[i]+=query(a[i]-1)
    add(a[i],1)
ans=0
for i in range(1,n+1):
    ans+=sums[i]*(sums[i]+1)//2
print(ans)

3.797. 差分 - AcWing题库

def add(l,r,v):
    b[l]+=v
    if r+1<=n:
        b[r+1]-=v
    return
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
b=[0 for i in range(n+1)]
for i in range(1,n+1):
    add(i,i,a[i])
for _ in range(m):
    l,r,c=map(int,input().split())
    add(l,r,c)
for i in range(1,n+1):
    b[i]+=b[i-1]
    print(b[i])

4.二维差分

二维差分的核心代码

def add(x1,y1,x2,y2,v):
    b[x1][y1]+=v
    b[x2+1][y2+1]+=v
    b[x2+1][y1]-=v
    b[x1][y2+1]-=v