看了《算法进阶指南》后按照作者的思路自己写了一份代码(可以保证正确性无误):
void init(int x,int v) {
int p=x-lowbit(x),add=(x-p)/2;
while(add) p+=add,c[x]=max(c[p],c[x]),add/=2;
c[x]=max(c[x],v);
}
原理就是每个节点的信息从它的子节点获得。
在main函数里这样写:for(int i=1;i<=n;i++) init(i,read())
有大佬说可以用前缀和来O(n)初始化,但是可以注意到我代码中是取max,所以前缀和这种方案行不通。
但是发现这样写的效率还不是O(nlogn)初始化呢qwq
是我代码写得常数太大了吗?有大佬有好的写法么=w=