为什么我看到许多大佬或是模板代码都是直接带着整个区间递归(区间查询/修改操作)。这样有什么好处吗?蒟蒻第一次写线段树,在每次递归时直接把给定的区间截成两段。
比如要递归 [3,5] 这个区间:
以下 [l,r,L,R] 表示正在查询/修改的区间和递归的区间。
大佬们或模板的:[3,5,1,5]->[3,5,1,3]->[3,5,3,3]->[3,5,4,5]->[3,5,5,5]->[3,5,4,4]
我的:[3,5,1,5]->[3,3,1,3]->[3,3,3,3]->[4,5,4,5]->[4,4,4,4]->[5,5,5,5]
而且我的 inrange 函数是这样的:
int inrange(int l,int r,int bh){
int L=t[bh].l,R=t[bh].r,mid=(L+R)/2;
if(r<=mid) return 1;
if(l>mid) return 2;
return 3;
}
似乎都能过,只是想知道大家这么做的原理是啥?