建设网站实训,网站开发工程师简历,企业网站推广 知乎,Wordpress 对比wagtailPowered by:NEFU AB-IN
Link 文章目录242. 一个简单的整数问题题意思路代码242. 一个简单的整数问题 题意 给定长度为 N的数列 A#xff0c;然后输入 M行操作指令。 第一类指令形如 C l r d#xff0c;表示把数列中第 l∼r个数都加 d 第二类指令形如 Q x#xff0c;表示询问…Powered by:NEFU AB-IN
Link 文章目录242. 一个简单的整数问题题意思路代码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])))
