萌新不会势能分析求助,下面这类题目的时间复杂度应当如何分析,有没有什么公式?
使用线段树维护一个长度为 nnn 的数列,共有 mmm 次区间修改操作和 qqq 次区间查询操作。设 aia_iai 能进行的有效操作数为 sis_isi,S=∑siS=\sum s_iS=∑si。
区间修改操作与本题做法相同:如果当前区间所有元素都不能进行有效操作,直接返回;否则递归到查询区间的叶子暴力修改。区间查询操作与普通线段树相同。
n,m,q,Sn,m,q,Sn,m,q,S 视为不同阶,合并两个儿子节点信息的时间复杂度视为 Θ(1)\Theta(1)Θ(1)。
有没有大佬教教/kel