树状数组单点操作+前缀K差分-＞区间K操作 -#131-#132
目录
区间乘
场景1.整数模运算
场景2.浮点数运算
#131. 树状数组 2 ：区间修改，单点查询
#132. 树状数组 3 ：区间修改，区间查询
树状数组底层逻辑探讨 / 模版代码-P3374-P3368-CSDN博客
在上一章最后我略带了原本只能单点操作的树状数组通过前缀和和差分实现了区间加
模板代码如下（以模板题P3368为例）
def lowbit(x):return x & -xdef init(a, tree1, tree2, n): #从数组a初始化d数组和d*i数组for i in range(1, n + 1):delta = a[i] - a[i - 1]add(tree1, n, i, delta)add(tree2, n, i, delta * (i - 1))def add(tree, n, x, v): #树状数组单点操作while x <= n:tree[x] += vx += lowbit(x)def query(tree, x): #树状数组区间查询（前缀和）#可用于d数组前缀和实现数组a的单点查询res = 0while x > 0:res += tree[x]x -= lowbit(x)return resdef range_add(tree1, tree2, n, l, r, v): #区间操作add(tree1, n, l, v) #操作1add(tree1, n, r + 1, -v)add(tree2, n, l, v * (l - 1)) #操作2add(tree2, n, r + 1, -v * r)def prefix_sum(tree1, tree2, x): #数组a从1到x区间的前缀和return query(tree1, x) * x - query(tree2, x)def range_sum(tree1, tree2, l, r): #数组a从l到r区间的和return prefix_sum(tree1, tree2, r) - prefix_sum(tree1, tree2, l - 1)n,m=map(int,input().split())a=[0]+list(map(int,input().split())) #下标从1开始t1=[0]*(n+2)
t2=[0]*(n+2)
init(a,t1,t2,n)for _ in range(m):te=tuple(map(int,input().split()))#用tuple方便解包if te[0]==1: #区间加l,r,v=te[1:]range_add(t1,t2,n,l,r,v)else:idx=te[1]val=query(t1,idx) #数组d前缀和实现数组a单点查询print(val)区间乘
和“通过前缀和实现区间和”类似，我们需要计算前缀乘积从而实现区间乘
def lowbit(x):return x & -xdef multiply_update(tree, n, x, v): # 树状数组单点乘操作while x <= n:tree[x] *= vx += lowbit(x)def multiply_query(tree, x): # 树状数组前缀乘积查询res = 1while x > 0:res *= tree[x]x -= lowbit(x)return resdef init(a, tree, n): # 初始化 f 数组，令 f[1] = a[1], f[i] = a[i] / a[i-1] (i>=2)# 树状数组 tree 下标 1~n 均初始化为 1for i in range(1, n + 1):tree[i] = 1for i in range(1, n + 1):if i == 1:factor = a[1]else:factor = a[i] / a[i - 1]multiply_update(tree, n, i, factor)def range_multiply(tree, n, l, r, v): # 区间乘法更新：区间 [l, r] 的元素均乘 vmultiply_update(tree, n, l, v) # f[l] 乘以 vif r + 1 <= n:multiply_update(tree, n, r + 1, 1 / v) # f[r+1] 乘以 1/vdef prefix_product(tree, x): # 数组 a 从 1 到 x 的前缀乘积return multiply_query(tree, x)def range_product(tree, l, r): # 区间 [l, r] 的乘积return prefix_product(tree, r) / prefix_product(tree, l - 1)
场景1.整数模运算
在数据较大、有溢出风险的情况下，我们通常选择模一个质数（例如 MOD = 10⁹+7），并用乘法逆元实现区间乘操作：
MOD = 10**9 + 7def lowbit(x):return x & -xdef modinv(x):return pow(x, MOD - 2, MOD)def multiply_update(tree, n, x, v):# 模运算下，更新 BIT 内元素：乘上 v (模 MOD)while x <= n:tree[x] = (tree[x] * v) % MODx += lowbit(x)def multiply_query(tree, x):res = 1while x > 0:res = (res * tree[x]) % MODx -= lowbit(x)return resdef init(a, tree, n):# 将树状数组初始化为乘法单位元1for i in range(1, n + 1):tree[i] = 1for i in range(1, n + 1):if i == 1:factor = a[1] % MODelse:# 计算相邻比值: a[i] / a[i-1] 变为 a[i] * modinv(a[i-1])factor = (a[i] * modinv(a[i-1])) % MODmultiply_update(tree, n, i, factor)def range_multiply(tree, n, l, r, v):# 区间 [l, r] 同时乘上 vmultiply_update(tree, n, l, v % MOD)if r + 1 <= n:multiply_update(tree, n, r + 1, modinv(v % MOD))def prefix_product(tree, x):return multiply_query(tree, x)def range_product(tree, l, r):# 区间乘积为前缀乘积之比return (prefix_product(tree, r) * modinv(prefix_product(tree, l - 1))) % MOD场景2.浮点数运算
浮点版本直接使用除法操作
def lowbit(x):return x & -xdef multiply_update(tree, n, x, v):while x <= n:tree[x] *= vx += lowbit(x)def multiply_query(tree, x):res = 1.0while x > 0:res *= tree[x]x -= lowbit(x)return resdef init(a, tree, n):for i in range(1, n + 1):tree[i] = 1.0for i in range(1, n + 1):if i == 1:factor = a[1]else:# 浮点除法直接计算相邻比值factor = a[i] / a[i - 1]multiply_update(tree, n, i, factor)def range_multiply(tree, n, l, r, v):multiply_update(tree, n, l, v)if r + 1 <= n:multiply_update(tree, n, r + 1, 1.0 / v)def prefix_product(tree, x):return multiply_query(tree, x)def range_product(tree, l, r):return prefix_product(tree, r) / prefix_product(tree, l - 1)
下面我们还是做几道题（但是由于用树状数组实现区间乘积的题目较少，一般都用线段树，所以我们还是先看看区间和的题目）
#131. 树状数组 2 ：区间修改，单点查询
https://loj.ac/p/131
这道题和P3368一个套路，直接套我文章开头的代码即可
#132. 树状数组 3 ：区间修改，区间查询
https://loj.ac/p/132
改模板代码中的query区间查询函数为range_sum函数即可
def lowbit(x):return x & -xdef init(a, tree1, tree2, n): #从数组a初始化d数组和d*i数组for i in range(1, n + 1):delta = a[i] - a[i - 1]add(tree1, n, i, delta)add(tree2, n, i, delta * (i - 1))def add(tree, n, x, v): #树状数组单点操作while x <= n:tree[x] += vx += lowbit(x)def query(tree, x): #树状数组从1到x区间的前缀和查询res = 0while x > 0:res += tree[x]x -= lowbit(x)return resdef range_add(tree1, tree2, n, l, r, v): #区间操作add(tree1, n, l, v) #操作1add(tree1, n, r + 1, -v)add(tree2, n, l, v * (l - 1)) #操作2add(tree2, n, r + 1, -v * r)def prefix_sum(tree1, tree2, x): #数组a从1到x区间的前缀和return query(tree1, x) * x - query(tree2, x)def range_sum(tree1, tree2, l, r): #数组a从l到r区间的和return prefix_sum(tree1, tree2, r) - prefix_sum(tree1, tree2, l - 1)n,m=map(int,input().split())
'''
a=[0]+list(map(int,input().split())) #下标从1开始
'''
t1=[0]*(n+2)
t2=[0]*(n+2)
'''
init(a,t1,t2,n)
'''
for _ in range(m):te=tuple(map(int,input().split()))#用tuple方便解包if te[0]==1:l,r,v=te[1:]range_add(t1,t2,n,l,r,v)else:l,r=te[1:]val=range_sum(t1,t2,l,r)print(val)