初学小白的理解，欢迎各路大神指正！！！

题目描述

假定有一个无限长的数轴，数轴上每个坐标上的数都是0。现在，我们首先进行n次操作，每次操作将某一位置 x上的数加 c。

接下来，进行m次询问，每个询问包含两个整数l和r，你需要求出在区间[l,r]之间的所有数的和。

解题思路：

离散化（映射）+前缀和

1、构造离散化-建立映射

• 离散什么呢？或者说映射什么呢？
• 原数组中所有涉及到的索引
• 这里包括操作数的索引和区间范围索引
• 具体操作：
• set():自带去重
• map{}:以原索引为键，现索引为值

2、构造差分-前缀和

• 通过原来操作数的坐标找到映射中的索引 a[i]+=c
• 通过原来左右边界的坐标找到映射中的索引 pre_sum[r]-pre_sum[l-1]

python 代码

# 输入解析
n, m = map(int, input().split())  # n次操作，m次查询
# 位置 x ,数 c
operations = [list(map(int, input().split())) for _ in range(n)]
# 左右边界坐标
queries = [list(map(int, input().split())) for _ in range(m)]

# 将所有要用到的坐标都存到这个集合里面去，set自带去重
coords=set()
for ops in operations:
    coords.add(ops[0])

for l,r in queries:
    coords.add(l)
    coords.add(r)
coords=sorted(coords)

# print(coords)

# 构造映射
idx_map={}
for i,val in enumerate(coords,start=1): # 从1开始，保持与“坐标”理解一致性
    idx_map[val]= i # 以原来的坐标为键，新索引为值

# 开始还原
# 差分数组
a=[0]*(len(coords) + 1)
for ops in operations:
    x,c = ops
    idx = idx_map[x] # 通过原来的坐标找到映射中的索引
    a[idx]+=c

# 前缀和数组
pre_sum=[0]*(len(coords) + 1)
for i in range(len(coords) + 1):
    pre_sum[i]=pre_sum[i-1]+a[i]

# print(pre_sum)

results=[]
# 处理查询
for l,r in queries:
    idx_l=idx_map[l] # 通过原来的坐标找到映射中的左边界索引
    idx_r=idx_map[r] # 通过原来的坐标找到映射中的右边界索引
    res = pre_sum[idx_r]- pre_sum[idx_l-1] # 前缀和求原区间l,r的和
    results.append(res)

# 输出结果
print('\n'.join(map(str, results)))