algorithm - 段树：延迟传播

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

Answer 2

Your answer is not correct. You need to do some sort of lazy update like here: http://p--np.blogspot.ro/2011/07/segment-tree.html . Else, if you do update(1,n, x) and query(4,5) you will get a wrong answer because the update has changed just the root node.