线段树
线段树一类题的合集，随训练持续更新。
线段树模板（区间修改 + 区间查询 + 懒标记）
用python重写下线段树模板，线段树的记忆点在于脑子里要有线段树，特点是自顶向下构建
class segment_tree:
def __init__(self, nums):
n = len(nums)
self.nums = nums
self.tree = [0] * 4 * n
self.tag = [0] * 4 * n
def update(self, root):
self.tree[root] = self.tree[root * 2] + self.tree[root * 2 + 1]
# lazy change
def down(self, left, right, root):
mid = (left + right) // 2
if self.tag[root] != 0:
self.tag[root * 2] += self.tag[root]
self.tag[root * 2 + 1] += self.tag[root]
self.tree[root * 2] += (mid - left + 1) * self.tag[root]
self.tree[root * 2 + 1] += (right - mid) * self.tag[root]
self.tag[root] = 0
# [A, B] add v
# change(A, B, v, 1, n, 1)
def change(self, A, B, v, left, right, root):
if A <= left <= right <= B:
self.tag[root] += v
self.tree[root] += (right - left + 1) * v
return
self.down(left, right, root)
mid = (left + right) // 2
if mid >= A:
self.change(A, B, v, left, mid, root * 2)
if mid + 1 <= B:
self.change(A, B, v, mid + 1, right, root * 2 + 1)
self.update(root)
# build(1, n, 1)
def build(self, left, right, root):
if left == right:
self.tree[root] = self.nums[left - 1]
return
mid = (left + right) // 2
self.build(left, mid, root * 2)
self.build(mid + 1, right, root * 2 + 1)
self.update(root)
# query(A, B, 1, n, 1)
def query(self, A, B, left, right, root):
if A <= left <= right <= B:
return self.tree[root]
self.down(left, right, root)
mid = (left + right) // 2
res = 0
if mid >= A:
res += self.query(A, B, left, mid, root * 2)
if mid + 1 <= B:
res += self.query(A, B, mid + 1, right, root * 2 + 1)
return res
import sys
n, m = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))
tree = segment_tree(nums)
tree.build(1, n, 1)
for _ in range(m):
a = list(map(int, sys.stdin.readline().split()))
# change
if len(a) == 4:
x = a[1]
y = a[2]
k = a[3]
tree.change(x, y, k, 1, n, 1)
# query
else:
x = a[1]
y = a[2]
res = tree.query(x, y, 1, n, 1)
print(res)
CF 339D - Xenia and Bit Operations（单点修改 + 分层切换运算）
https://codeforces.com/problemset/problem/339/D
题意：2^n个数组成的数组，m次单点修改带查询。数组计算规则是相邻两数先做或运算得到新数组，新数组相邻两数再做异或运算，... ，最后得到一个数即为查询结果。
看到单点修改首先想到线段树或树状数组，再观察到2^n形式正好是一颗满节点的线段树，运算选择取决于线段树层数，叶子节点上一层或运算，再上一层异或，...，询问结果实际是问根节点的值
因此在单点修改的线段树模板上只需要根据层数切换update的方式即可
import sys
n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
st = {}
x = n
res = 0
while x >= 0:
st[int(pow(2, x))] = (res ^ 1)
x -= 1
res ^= 1
def check(num):
x = 0
while x <= n:
i = int(pow(2, x))
j = int(pow(2, x + 1))
if i <= num < j:
return st[i]
x += 1
class sengment_tree:
def __init__(self, nums):
self.n = len(nums)
self.nums = nums
self.tree = [0] * 4 * self.n
def update(self, root):
if check(root) == 1:
self.tree[root] = self.tree[root * 2] ^ self.tree[root * 2 + 1]
else:
self.tree[root] = self.tree[root * 2] | self.tree[root * 2 + 1]
def build(self, left, right, root):
if left == right:
self.tree[root] = self.nums[left - 1]
return
mid = (left + right) // 2
self.build(left, mid, root * 2)
self.build(mid + 1, right, root * 2 + 1)
self.update(root)
def change(self, pos, v, left, right, root):
if left == right:
self.tree[root] = v
return
mid = (left + right) // 2
if pos <= mid:
self.change(pos, v, left, mid, root * 2)
if pos >= mid + 1:
self.change(pos, v, mid + 1, right, root * 2 + 1)
self.update(root)
def query(self, A, B, left, right, root):
if A <= left <= right <= B:
return self.tree[root]
mid = (left + right) // 2
res = 0
if A <= mid:
if check(root):
res ^= self.query(A, B, left, mid, root * 2)
else:
res |= self.query(A, B, left, mid, root * 2)
if B >= mid + 1:
if check(root):
res ^= self.query(A, B, mid + 1, right, root * 2 + 1)
else:
res |= self.query(A, B, mid + 1, right, root * 2 + 1)
return res
tree = sengment_tree(a)
tree.build(1, int(pow(2, n)), 1)
for _ in range(m):
p, b = map(int, sys.stdin.readline().split())
tree.change(p, b, 1,int(pow(2, n)), 1)
res = tree.query(1, int(pow(2, n)), 1, int(pow(2, n)), 1)
print(res)