关于树状数组O(n)初始化

看了《算法进阶指南》后按照作者的思路自己写了一份代码（可以保证正确性无误）：

CPP

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=

讨论操作