【题目来源】AcWing256. 最大异或和 - AcWing题库【题目描述】给定一个非负整数序列a aa初始长度为N NN。有M MM个操作有以下两种操作类型A x添加操作表示在序列末尾添加一个数x xx序列的长度N NN增大1 11。Q l r x询问操作你需要找到一个位置p pp满足l ≤ p ≤ r l≤p≤rl≤p≤r使得KaTeX parse error: Undefined control sequence: \ at position 5: a[p]\̲ ̲xor\ a[p1]\ xo…最大输出这个最大值。【输入】第一行包含两个整数N NNM MM含义如问题描述所示。第二行包含N NN个非负整数表示初始的序列A AA。接下来M MM行每行描述一个操作格式如题面所述。【输出】每个询问操作输出一个整数表示询问的答案。每个答案占一行。【输入样例】5 5 2 6 4 3 6 A 1 Q 3 5 4 A 4 Q 5 7 0 Q 3 6 6【输出样例】4 5 6【核心思想】问题分析给定一个动态增长的非负整数序列支持在末尾添加元素和区间查询操作。查询要求在区间[ l , r ] [l, r][l,r]内找到一个位置p pp使得a [ p ] ⊕ a [ p 1 ] ⊕ … ⊕ a [ N ] ⊕ x a[p] \oplus a[p1] \oplus \ldots \oplus a[N] \oplus xa[p]⊕a[p1]⊕…⊕a[N]⊕x最大。利用前缀异或和转化后问题变为在区间[ l − 1 , r − 1 ] [l-1, r-1][l−1,r−1]内找到一个前缀异或和s [ p − 1 ] s[p-1]s[p−1]使得s [ p − 1 ] ⊕ ( s [ N ] ⊕ x ) s[p-1] \oplus (s[N] \oplus x)s[p−1]⊕(s[N]⊕x)最大。这是一个**可持久化字典树Persistent Trie**问题核心在于维护历史版本以支持区间限制下的最大异或查询。算法选择前缀异或和转化令s [ i ] a [ 1 ] ⊕ a [ 2 ] ⊕ … ⊕ a [ i ] s[i] a[1] \oplus a[2] \oplus \ldots \oplus a[i]s[i]a[1]⊕a[2]⊕…⊕a[i]则a [ p ] ⊕ … ⊕ a [ N ] s [ p − 1 ] ⊕ s [ N ] a[p] \oplus \ldots \oplus a[N] s[p-1] \oplus s[N]a[p]⊕…⊕a[N]s[p−1]⊕s[N]查询转化为求max ⁡ l − 1 ≤ p − 1 ≤ r − 1 { s [ p − 1 ] ⊕ C } \max_{l-1 \leq p-1 \leq r-1} \{s[p-1] \oplus C\}maxl−1≤p−1≤r−1​{s[p−1]⊕C}其中C s [ N ] ⊕ x C s[N] \oplus xCs[N]⊕x可持久化字典树Persistent Trie / 主席树每个版本对应一个前缀异或和集合通过路径复制实现O ( log ⁡ V ) O(\log V)O(logV)的版本创建V VV为数值范围贪心高位优先在字典树上从高位到低位优先走与目标值当前位不同的分支使异或结果最大关键步骤前缀异或和预处理s [ i ] s [ i − 1 ] ⊕ a i s[i] s[i-1] \oplus a_is[i]s[i−1]⊕ai​其中s [ 0 ] 0 s[0] 0s[0]0问题转化查询Q ( l , r , x ) Q(l, r, x)Q(l,r,x)等价于在集合{ s [ 0 ] , s [ 1 ] , … , s [ r − 1 ] } \{s[0], s[1], \ldots, s[r-1]\}{s[0],s[1],…,s[r−1]}中找到下标≥ l − 1 \geq l-1≥l−1的元素与C s [ N ] ⊕ x C s[N] \oplus xCs[N]⊕x异或最大可持久化字典树构建第i ii个版本r o o t [ i ] root[i]root[i]包含前缀异或和s [ 0 ] , s [ 1 ] , … , s [ i ] s[0], s[1], \ldots, s[i]s[0],s[1],…,s[i]插入s [ i ] s[i]s[i]时从高位到低位第23 2323位到第0 00位复制旧版本未修改的分支创建新节点存储当前位每个节点维护m a x _ i d max\_idmax_id以该节点为根的子树中最大的下标编号查询操作从版本r o o t [ r − 1 ] root[r-1]root[r−1]的根节点出发保证只考虑下标≤ r − 1 \leq r-1≤r−1的元素从高位到低位贪心若与C CC当前位不同的分支中存在m a x _ i d ≥ l − 1 max\_id \geq l-1max_id≥l−1的节点则走该分支否则走相同分支确保所选元素下标≥ l − 1 \geq l-1≥l−1添加操作序列长度N NN增加计算新的s [ N ] s[N]s[N]基于r o o t [ N − 1 ] root[N-1]root[N−1]创建新版本r o o t [ N ] root[N]root[N]时间/空间复杂度时间复杂度O ( ( N M ) log ⁡ V ) O((N M) \log V)O((NM)logV)每次插入和查询均为O ( log ⁡ V ) O(\log V)O(logV)V VV为数值范围本题中V 2 24 V 2^{24}V224故为O ( 24 ) O(24)O(24)空间复杂度O ( ( N M ) log ⁡ V ) O((N M) \log V)O((NM)logV)每个版本新增O ( log ⁡ V ) O(\log V)O(logV)个节点可持久化字典树的核心思想版本化历史快照每个版本r o o t [ i ] root[i]root[i]保存前i ii个前缀异或和的完整字典树结构通过路径复制实现O ( log ⁡ V ) O(\log V)O(logV)的空间增量路径复制策略插入新值时只修改从根到叶子的一条路径上的节点其余分支直接引用旧版本节点实现空间高效的历史版本维护下标约束的贪心查询利用m a x _ i d max\_idmax_id数组在遍历过程中实时判断某个分支是否存在满足下标限制的元素将区间限制转化为版本选择 分支可行性判断前缀异或的区间转化将区间异或查询通过前缀和差分转化为单点查询使得字典树可以处理动态区间最大异或问题适用于动态数组的区间最大/最小异或查询、带历史版本的集合查询类问题【算法标签】#主席树【代码详解】#includebits/stdc.husingnamespacestd;constintN600005,MN*25;// N: 最大序列长度; M: 字典树最大节点数intn,m;// n: 序列长度; m: 操作次数ints[N];// s[i]: 前缀异或和s[i] a[1] xor a[2] xor ... xor a[i]inttr[M][2];// tr[p][0/1]: 字典树节点 p 的左右子节点0/1 分支intmax_id[M];// max_id[p]: 以节点 p 为根的子树中最大的下标编号introot[N];// root[i]: 第 i 个版本的字典树根节点intidx;// idx: 字典树节点计数器voidinsert(inti,intk,intp,intq)// 可持久化字典树插入i: 下标k: 当前位p: 旧版本节点q: 新版本节点{if(k0)// 已处理完所有位到达叶子{max_id[q]i;// 记录该路径对应的最大下标return;}intvs[i]k1;// 取出 s[i] 的第 k 位if(p)// 如果旧版本存在复制旧版本的另一分支tr[q][v^1]tr[p][v^1];tr[q][v]idx;// 创建新版本当前位的子节点insert(i,k-1,tr[p][v],tr[q][v]);// 递归插入下一位max_id[q]max(max_id[tr[q][0]],max_id[tr[q][1]]);// 更新当前节点的最大下标}intquery(introot,intC,intL)// 查询操作root: 版本根节点C: 目标异或值L: 下标下限{intproot;// 从版本根节点开始for(inti23;i0;i--)// 从高位到低位贪心优先走与 C 当前位不同的分支{intvCi1;// 取出 C 的第 i 位if(max_id[tr[p][v^1]]L)// 如果异或分支v^1中存在下标 L 的数ptr[p][v^1];// 走异或分支使结果更大elseptr[p][v];// 否则走相同分支}returnC^s[max_id[p]];// 返回 C 与最优前缀异或和的结果}intmain(){cinnm;// 读入初始序列长度和操作次数max_id[0]-1;// 初始化空节点的 max_id 为 -1root[0]idx;// 创建第 0 个版本空序列insert(0,23,0,root[0]);// 插入 s[0] 0for(inti1;in;i)// 读入初始序列并建立可持久化字典树{intx;// x: 当前读入的数cinx;s[i]s[i-1]^x;// 计算前缀异或和root[i]idx;// 创建第 i 个版本insert(i,23,root[i-1],root[i]);// 基于上一版本插入 s[i]}charop;// op: 操作类型intl,r,x;// l, r: 区间; x: 操作数值while(m--)// 循环处理 m 次操作{cinop;// 读入操作类型if(opA)// 操作 A在序列末尾添加一个数{cinx;n;// 序列长度加一s[n]s[n-1]^x;// 更新前缀异或和root[n]idx;// 创建新版本insert(n,23,root[n-1],root[n]);// 基于上一版本插入}else// 操作 Q询问操作{cinlrx;// 查询版本 root[r-1] 中满足下标 l-1 且与 (s[n]^x) 异或最大的值coutquery(root[r-1],s[n]^x,l-1)endl;}}return0;}【运行结果】5 5 2 6 4 3 6 A 1 Q 3 5 4 4 A 4 Q 5 7 0 5 Q 3 6 6 6