algorithm - 线段树 : Lazy propagation

Question

在整数数组(大小为 10^5)中，操作如下...

1. 对从索引 L 到 R 的每个元素按特定数字 X 进行按位异或运算
2. 求从索引 L 到 R 的数字之和。

我如何使用线段树和惰性传播来做到这一点？

Answer 1

我会在每个节点上保留 32 个整数，告诉我子节点的二进制表示的每个位置有多少个整数。

要对段节点进行异或，只需反转每个位置(对于 X 中的每个位 1)有多少个。

for i in range(32):
    if X&(1<<i):
        N[i] = (R-L+1)-N[i]. 

要计算总和，

s = 0
for i in range(32):
    s |= ((N[i]+carry)%2) << i
    carry = (N[i]+carry)/2