可持久化字典树与可持久化线段树类似。
解决的问题都是类似于“有限制的前缀和”，或二维问题。
而可持久化字典树更多的是解决异或问题，即运用01字典树。
解决异或最大问题，贪心地在字典树上选择。
例题
用前缀异或和把最大的区间异或和转化成单点。
想要与 \(x\) 异或后最大，就从高到低 \(x\) 在二进制上的每一位，贪心的查找在这一位能不能取到与 \(x\) 相反的值。
这里的查找实际上是检验贪心的取法会不会在后面出现问题。
单点有 \(l,r\) 的限制，就用可持久化来解决。
可持久化字典树
发布时间 2023-09-13 20:21:29作者: cqbzwwh