在query()中合并左右两个查询结果时,需要计算左查询区间的长度的奇偶性。左查询区间的长度由其左右端点下标得到。警惕下标的计算步骤。
SegTree segtree_range_query(const int root, const int &l, const int &r) {
if(l <= segtree[root].l && r >= segtree[root].r) { return segtree[root]; }
int m = (segtree[root].l + segtree[root].r) / 2;
if(r <= m) { return segtree_range_query(root * 2, l, r); }
if(l > m) { return segtree_range_query(root * 2 + 1, l, r); }
const SegTree query_l = segtree_range_query(root * 2, l, r), query_r = segtree_range_query(root * 2 + 1, l, r);
SegTree query;
query.v_lsum = query_l.v_lsum; query.v_rsum = query_l.v_rsum;
query.l = std::max(segtree[root].l, l); // 易错点
query.r = std::min(segtree[root].r, r); // 易错点
// 错误写法: if((m - segtree[root].l + 1) % 2 == 1) {
// 错误写法: if((m - l + 1) % 2 == 1) {
// 正确写法: if((m - std::max(segtree[root].l, l) + 1) % 2 == 1) {
if((query_l.r - query_l.l + 1) % 2 == 1) { // 正确写法
query.v_lsum ^= query_r.v_rsum;
query.v_rsum ^= query_r.v_lsum;
} else {
query.v_lsum ^= query_r.v_lsum;
query.v_rsum ^= query_r.v_rsum;
}
return query;
}