ACwing802-离散化-python-(数组数组+离散化)

比较难理解的一道题。我们首先对所有要进行添加操作的坐标进行离散化，用树状数组保存。当我们查询的时候，找到左右侧的端点，再利用树状数组求和即可。 AC代码

global a,lth
global tree
def low_bound(l,r,val):
    while l<=r:
        mid=l+r>>1
        if val<=a[mid]:
            r=mid-1
        else:
            l=mid+1
    return l
def lowbit(x):
    return x&(-x)
def add(x,val):
    while x<=lth:
        tree[x]+=val
        x+=lowbit(x)
def query(x):
    ans=0
    while x:
        ans+=tree[x]
        x-=lowbit(x)
    return ans
n,m=map(int,input().split())
op=[0]*n

dot=set()
for i in range(n):
    x,c=map(int,input().split())
    op[i]=[x,c]
    dot.add(x)
a=list(dot)
a.sort()
a.insert(0,float("-inf"))
lth=len(a)-1

tree=[0]*(lth+1)
for i in range(n):
    x,c=op[i][0],op[i][1]
    index=low_bound(0,lth,x)
    add(index,c)

for i in range(m):
    l,r=map(int,input().split())
    lindex=low_bound(0,lth,l)
    
    ans1=query(lindex-1)

    rindex=low_bound(0,lth,r)
    if rindex<=lth and a[rindex]==r:
        ans2=query(rindex)
    else:
        ans2=query(rindex-1)
    print(ans2-ans1)