关于线段树写法(不是调代码)

学术版

zgy_123 @ 2024-09-19 22:21:48

  1. 如果我有一个询问只单点的线段树,能否只在叶子上存信息,其他节点只存懒标记,减少常数?个人认为可行,但目前没见过这么写的。
  2. 如果在上一问条件下,在其他节点也存信息,那么存什么可以在满足答案正确的情况下减少常数?(比如存区间和、区间最大值、区间最小值对于单点显然是没有区别的)
  3. 如果线段树的上、下传标记会调用另一棵线段树(比如区间加上另一棵线段树),这样能否写在结构体内置函数里?

看情况悬关。


by XiaoYiii @ 2024-09-19 22:24:20

@zgy_123 1、2 可以试试标记永久化


by StarLbright40 @ 2024-09-19 22:25:39

你应该是见少了。

评价为别急,没见过说明用不上。


by jr_zch @ 2024-09-19 23:09:10

  1. 显然是可以的,我就经常这样,没见过说明题做少了。

  2. 想存什么存什么,存个区间和常数小,虽然区别不大。

  3. 可以重载运算符?

@zgy_123


by xiezheyuan @ 2024-09-19 23:20:08

@zgy_123 必须行

我见过类似的题目 spoj NSUBSTR - Substrings

每个节点只存tag因为我只查询叶子


by xiezheyuan @ 2024-09-19 23:23:36

@zgy_123 和金钩爷一样的道理,这些东西如果不知道要不要用先放在大脑里藏起来,等到遇到了题目自然就可以试试了。


|