预计阅读时间：6 分钟
线段树
数据结构里的高达：拼装麻烦，但拼好之后区间问题基本横着走。本合集收录线段树题目，随训练持续补完。
线段树模板（区间修改 + 区间查询 + 懒标记）
用 Python 重写的线段树模板。线段树的记忆点在于写代码时脑子里要有那棵树——自顶向下构建，节点 root 的左右孩子是 2*root 和 2*root+1，懒标记在下探时才向下推。
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 按层数切换运算方式。代码里先预处理出「节点编号所在的 2 的幂区间 → 该层运算类型」的对照表 st，check(root) 据此判定当前节点该用或还是异或。
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 segment_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 = segment_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)
未完待续，本合集随训练进度持续补完。
本文由 aboom 原创，转载请注明出处。