给定数组执行增删全局异或三类查询求每次操作后总和，找O(nlogn)解法

完全可以用比线段树更简单的方法实现，时间复杂度甚至优于要求的O(nlogn)，核心思路是利用异或的位独立性特性按位统计贡献。

核心原理 #

整数的总和可以拆分为每一个二进制位的贡献之和：总和 = Σ（第k位上1的个数 * 2^k）。而异或操作对每一位的影响是独立的：如果全局异或值的第k位为1，那么当前所有元素的第k位会0变1、1变0，该位的1的个数直接变成「总元素数 - 原来该位1的个数」，无需遍历修改所有元素。

所需维护的变量 #

• 存储映射：用数组或哈希表store，记录每个合法下标对应的存储值（注意存储值不是元素的实际展示值，实际展示值 = 存储值 ^ 全局异或标记），同时标记下标是否已被删除
• 位计数数组cnt[31]：cnt[k]表示当前所有未删除元素的存储值的第k位为1的总个数（按int整数最高31位计算即可，若要支持更大整数可扩展位数）
• 全局异或标记global_xor：记录当前全局生效的异或值
• 总元素计数m：记录当前未被删除的元素总数

三类操作的实现逻辑 #

每次操作完成后，按以下规则计算当前总和输出即可：
对每一位k，若global_xor的第k位为1，当前实际1的个数为m - cnt[k]，否则为cnt[k]，累加每一位的贡献（个数 * 2^k）得到总和。

操作1 （添加元素X到末尾，新下标为new_id） #

• 计算存储值：val = X ^ global_xor（保证实际展示值为val ^ global_xor = X，和全局异或状态匹配）
• 遍历每一位k，若val的第k位为1，cnt[k] += 1
• 存储store[new_id] = val，总元素数m += 1
• 计算并输出当前总和

操作2 （删除下标为Y的元素） #

• 取出该下标对应的存储值val = store[Y]，标记该下标已删除
• 遍历每一位k，若val的第k位为1，cnt[k] -= 1
• 总元素数m -= 1
• 计算并输出当前总和

操作3 （全局所有元素异或Z） #

• 直接更新全局异或标记：global_xor ^= Z，无需修改其他任何数据
• 计算并输出当前总和

复杂度分析 #

• 单次操作1、2的时间复杂度为O(31) = O(1)，操作3的时间复杂度为O(1)
• 单次总和计算的时间复杂度为O(31) = O(1)
• 整体时间复杂度为O(n + Q)，远优于要求的O(nlogn)，空间复杂度为O(n + Q)（存储所有出现过的下标即可）

内容的提问来源于stack exchange，提问作者unglinh279