题解 | #【模板】前缀和#

【模板】前缀和

https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf

N = 100100 # 假设最大数量稍微大于1e5 树状数组解法
f = [0] * N

def lowbit(x):
    return x & (-x)
def upd(pos, v, n):
    while pos <= n:
        f[pos] += v
        pos += lowbit(pos)
def get(pos):
    res = 0
    while pos > 0:
        res += f[pos]
        pos -= lowbit(pos)
    return res

n,q = map(int, input().split())
data = list(map(int, input().split()))

for i in range(0, n):
    upd(i + 1, data[i], n)

for _ in range(q):
    a, b = map(int, input().split())
    print(get(b) - get(a - 1))

全部评论

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务