线段树
  • 板块学术版
  • 楼主A_small_WA
  • 当前回复13
  • 已保存回复14
  • 发布时间2025/1/16 10:07
  • 上次更新2025/1/16 13:48:25
查看原帖
线段树
1124323
A_small_WA楼主2025/1/16 10:07

为什么我看到许多大佬或是模板代码都是直接带着整个区间递归(区间查询/修改操作)。这样有什么好处吗?蒟蒻第一次写线段树,在每次递归时直接把给定的区间截成两段。

比如要递归 [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;
}
//1:只有左 2:只有右 3:左右都有

似乎都能过,只是想知道大家这么做的原理是啥?

2025/1/16 10:07
加载中...