摘要
Title: 242. 一个简单的整数问题
Tag: 树状数组、差分
Memory Limit: 64 MB
Time Limit: 1000 ms

242. 一个简单的整数问题

题意

给定长度为 N的数列 A，然后输入 M行操作指令。
第一类指令形如 C l r d，表示把数列中第 l∼r个数都加 d
第二类指令形如 Q x，表示询问数列中第 x个数的值。
对于每个询问，输出一个整数表示答案
思路

树状数组 + 差分，实现区间修改 + 单点查询
其实就是对差分数组进行原先树状数组的操作，维护差分数组
- 区间修改就是 add(l, d) add(r + 1, -d)
- 单点查询就是，对差分数组求前缀和，也就是单点查询了
如要实现区间查询，详见 link

代码

'''
Author: NEFU AB-IN
Date: 2023-03-26 11:48:05
FilePath: \Acwing\242\242.py
LastEditTime: 2023-03-26 11:55:10
'''
# import
import sys, math
from collections import Counter, deque
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right

# Final
N = int(1e5 + 10)
INF = int(2e9)

# Define
sys.setrecursionlimit(INF)
read = lambda: map(int, input().split())

# —————————————————————Division line ————————————————————————————————————————
tr = [0] * N


def lowbit(x):
    return x & -x


def add(x, v):
    while x < N:
        tr[x] += v
        x += lowbit(x)


def query(x):
    res = 0
    while x:
        res += tr[x]
        x -= lowbit(x)
    return res


n, m = read()
a = [0] + list(read())
for i in range(1, n + 1):
    add(i, a[i] - a[i - 1])

for _ in range(m):
    op = list(input().split())
    if op[0] == 'C':
        l, r, d = map(int, op[1:])
        add(l, d)
        add(r + 1, -d)
    else:
        print(query(int(op[1])))

242. 一个简单的整数问题

题意

思路

代码