对于这个问题已经有一些帖子解答：请问为什么一定要先加入一个0，hack，但我希望出现更加详细的解答，也方便解答后人的疑惑。

本人做法为可持久化 Trie，当查询为 $[1,2]$ 时，实际上在 Trie 树上查询的两个点是一个不存在的点和 $rt_1$。如果最开始没有插入 $0$ 并且 $a_1\ne 0$ 的话，Trie 树查询会误以为只能选 $a_1$ 进行异或，但实际上选 $p=1$ 即前缀为 $0$ 时也是合法的，因此最开始要插入一个 $0$ 表示选 $p=1$ 也是合法的。