242. 一个简单的整数问题

Powered by:NEFU AB-IN

Link

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] * Ndef lowbit(x):return x & -xdef add(x, v):while x < N:tr[x] += vx += lowbit(x)def query(x):res = 0while x:res += tr[x]x -= lowbit(x)return resn, 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])))