Powered by:NEFU AB-IN

Link

242. 一個(gè)簡(jiǎn)單的整數(shù)問(wèn)題

• 題意

  給定長(zhǎng)度為 N的數(shù)列 A，然后輸入 M行操作指令。
  第一類指令形如 C l r d，表示把數(shù)列中第 l～r個(gè)數(shù)都加 d
  第二類指令形如 Q x，表示詢問(wèn)數(shù)列中第 x個(gè)數(shù)的值。
  對(duì)于每個(gè)詢問(wèn)，輸出一個(gè)整數(shù)表示答案

• 思路

  樹狀數(shù)組 + 差分，實(shí)現(xiàn)區(qū)間修改 + 單點(diǎn)查詢
  其實(shí)就是對(duì)差分?jǐn)?shù)組進(jìn)行原先樹狀數(shù)組的操作，維護(hù)差分?jǐn)?shù)組

  • 區(qū)間修改就是 add(l, d) add(r + 1, -d)
  • 單點(diǎn)查詢就是，對(duì)差分?jǐn)?shù)組求前綴和，也就是單點(diǎn)查詢了

  如要實(shí)現(xiàn)區(qū)間查詢，詳見(jiàn) 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])))