```cpp
void build () {
for (int i = 1; i <= n; i++) {
t[i] += a[i]
t[i + (i & -i)] += t[i];
}
}
```
好像是这样
by wheneveright @ 2021-08-04 21:44:46
线段树不香吗
by Union_of_Britain @ 2021-08-04 21:46:48
@[kkksc0100_juruo](/user/342076) 相比于树状数组…线段树的码量未免……/jk
by cnyh_673 @ 2021-08-04 21:48:18
@[kkksc0100_juruo](/user/342076) 搞的线段树比树状数组快空间小
by wheneveright @ 2021-08-04 21:48:23
@[kkksc0100_juruo](/user/342076) 而且人家搁着问树状数组你回答个线段树
by wheneveright @ 2021-08-04 21:49:42
![](//图.tk/9)
by Union_of_Britain @ 2021-08-04 21:49:55
@[wheneveright](/user/189351) 谢谢大佬orz
by Zlc晨鑫 @ 2021-08-04 23:13:32
@[wheneveright](/user/189351) 但是这样是O(N)吗?
```cpp
// O(N)建树
for (int i = 1; i <= n; ++i)
for (int j = i - lowbit(i) + 1; j <= i; ++j)
c[i] += a[j];
```
by Zlc晨鑫 @ 2021-08-04 23:13:59
还是O(NlogN)?
by Zlc晨鑫 @ 2021-08-04 23:14:44
@[Zlc晨鑫](/user/297555) 这个是带一个log的
by wheneveright @ 2021-08-05 07:46:54