2020-2021:teams:farmer_john:2020暑假精选题目:数据结构
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020暑假精选题目:数据结构 [2020/09/05 11:22] jjleo [题解] |
2020-2021:teams:farmer_john:2020暑假精选题目:数据结构 [2020/09/05 11:23] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 33: | 行 33: | ||
| 考虑对1的操作，因为是单点赋值，我们直接将$a_{i\text{^}x}$改为对应的值即可。 | 考虑对1的操作，因为是单点赋值，我们直接将$a_{i\text{^}x}$改为对应的值即可。 | ||
| - | 考虑对4的操作，我们现在需要求出$$\sum_{i=l}^r a_{i\text{^}x}$$我们可以先建出一棵$[0,2^n-1]$的线段树，可以看除这棵树所有节点的对应的区间长度均为$2$的次幂。接下来将$[l,r]$类似线段树查询那样分成$O(\log n)$个区间进行查询。对于每一个区间我们可以发现都有如下性质：该区间内所有数的二进制可以表示成如下形式$$P00 \cdots 00, P00 \cdots 01, P00 \cdots 10, \ldots , P11 \cdots 11$$其中$P$是一个公共前缀，所以它们在异或$x$后也对应一个连续的区间，设$Q$是一个前缀，为$P$这个前缀与$x$对应位异或所得，则对应的连续区间为$$Q00 \cdots 00, Q00 \cdots 01, Q00 \cdots 10, \ldots , Q11 \cdots 11$$因为后面的部分每一位都不相同，由异或的性质可得它们依旧构成形如上述的序列，因此我们再开一个线段树/树状数组查询$[$Q00 \cdots 00,,$Q11 \cdots 11,]$的值即可，总复杂度$O(n \log ^2 n)$。 | + | 考虑对4的操作，我们现在需要求出$$\sum_{i=l}^r a_{i\text{^}x}$$我们可以先建出一棵$[0,2^n-1]$的线段树，可以看除这棵树所有节点的对应的区间长度均为$2$的次幂。接下来将$[l,r]$类似线段树查询那样分成$O(\log n)$个区间进行查询。对于每一个区间我们可以发现都有如下性质：该区间内所有数的二进制可以表示成如下形式$$P00 \cdots 00, P00 \cdots 01, P00 \cdots 10, \ldots , P11 \cdots 11$$其中$P$是一个公共前缀，所以它们在异或$x$后也构成了一个连续的区间，设$Q$是一个前缀，为$P$这个前缀与$x$对应位异或所得，则对应的连续区间为$$Q00 \cdots 00, Q00 \cdots 01, Q00 \cdots 10, \ldots , Q11 \cdots 11$$因为后面的部分两两都不相同，由异或的性质可得它们依旧构成形如上述的序列，因此我们再开一个线段树/树状数组查询$[Q00 \cdots 00,Q11 \cdots 11]$的值即可，总复杂度$O(n \log ^2 n)$。 |
2020-2021/teams/farmer_john/2020暑假精选题目/数据结构.1599276131.txt.gz · 最后更改: 2020/09/05 11:22 由 jjleo
