由于要查询左闭右开区间[l, r)内的左端点数量,所以当l==r时,调用segtree_query(根节点=1, l, r-1, 左端点)时会出现查询闭区间[l, l-1]的情况。
输入:
4 2
1 1 3
2 1 1
输出:
1
专打线段树查询:
// 查询闭区间[l, r]内的左/右端点数量
int segtree_query(const int root, const int &l, const int &r, const int &type) {
if(l <= segtree[root].l && r >= segtree[root].r) { return segtree[root].v_sum[type]; }
int m = (segtree[root].l + segtree[root].r) / 2;\
// 这种方式逃过一劫,l>r时总能保证在叶子节点处时,两个if分支都不执行,从而return 0;
// int query = 0;
// if(l <= m) { query += segtree_query(root * 2, l, r, type); }
// if(r > m) { query += segtree_query(root * 2 + 1, l, r, type); }
// return query;
// 这种方式无限递归,爆栈
if(r <= m) { return segtree_query(root * 2, l, r, type); }
if(l > m) { return segtree_query(root * 2 + 1, l, r, type); }
return segtree_query(root * 2, l, r, type) + segtree_query(root * 2 + 1, l, r, type);
}