转转表示一脸懵逼。
1
2
3
4
5
6
7
8
9
| int query(int p,int l,int r,int ql,int qr)
{
++cnt;
if(ql<=l&&r<=qr)return val[p];
int mid=(l+r)>>1;
if(qr<=mid)return query(ls,l,mid,ql,qr);
if(ql>mid)return query(rs,mid+1,r,ql,qr);
return max(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
}
|
称单个线段树结点管辖的范围为直接区间，函数会在区间的 $O(\log n)$ 个极大直接区间处返回。
最后一句话每执行一次都会将返回分为两部分，而另外两句话舍去的空区间同样也是全局除查询区间外的极大直接区间。
所以单次查询的时间复杂度为 $O(\log n)$。
1
2
3
4
5
6
7
8
9
10
| #define Max(x,y)((x)>(y)?x:y)
int query(int p,int l,int r,int ql,int qr)
{
++cnt;
if(ql<=l&&r<=qr)return val[p];
int mid=(l+r)>>1;
if(qr<=mid)return query(ls,l,mid,ql,qr);
if(ql>mid)return query(rs,mid+1,r,ql,qr);
return Max(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
}
|
注意到取最大值变成了宏定义，最值取到的调用会被递归两次。
补齐成为二的幂次，多出来的位置看做插入线段树底层，不会影响到上层结构就没有问题了。
以极大直接区间作为自变量，$T(n)=2T(n-1)+O(1)=O(2^n)$。
但极大直接区间数量的常数跑到了最终时间复杂度的指数那里。把最大的具体数量写一写：
1
2
| 1 2 3 4 5 6 7 8 9 10 ...
1 2 2 3 3 4 3 4 4 5 ...
|
看不出来。
虽然最大极大直接区间可能存在两个，但一旦分成两半递归后一侧就会一直是长度大于一半的最大极大直接区间，所以最坏就是最大值取在端点。
以区间长度作为自变量，$T(n)=2T(n/2)+O(1)=O(n)$。