原文 / 关注不屈三叶虫喵，关注不屈三叶虫谢谢喵
省流：本文介绍一种简单实现的线段树及其原理，运行效率极高。另外还有其改为任意叉的扩展。
考虑给定一个区间的编号，对其建线段树。
抛弃传统二叉树形式，只是利用其编号：
分块，把编号 i 的点放进编号为 \lfloor i/2\rfloor 的块中。所有完整的块（块大小为 2）构成一个区间，对其递归建线段树。不完整的块，是这个区间的左右侧，是不完整的块，无需进入下一层。
你考虑做区间操作的时候会发生什么：如果左端点在散块，就暴力做这个散块，右端点同理。所以确实可以扔掉。
然后为了方便我们令初始区间为 [n,2n)，这样所有块的编号都是两两不同的（所有层的所有块）。这里选择这个区间的原因是我们需要保证 [l,r) 中 (r-1)/2<l，这是最小的区间。
然后我们发现此时等价线段树上 i 的父亲为 \lfloor i/2\rfloor。不过请注意，有些父亲不一定是有意义的，如果一个点被分到的块是散块，从而没有递归进入下一层，那么它没有父亲。
所以这个东西的结构其实是个森林，所有根的父亲其实是是没有用的，包括大多数时候的 1 号结点，所以在信息有顺序时不能用 1 表示全局信息！
所以单点修改同一般线段树，但我们不需要把所有叶子处理到同一层，只需要给编号 +\ n。
区间就是，把散块做了，然后递归到下一层，同块时停止，然后处理一下这个最后的块。
其实最后一个块不用这么复杂，因为每个块的大小显然不超过 2，所以只需要在 l=r 时停止（注意是左闭右开区间）。
具体实现：l \bmod 2\neq 0 时说明在一个散块中，r 也是一致的（这里体现左闭右开的好处）。散块大小显然为 1。
代码中为 0 开始的左闭右开区间。
void update(int x, int d) {
for (x += n; x; x >>= 1) sgt[x] += d;
}
int query(int l, int r) {
int ans = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) ans += sgt[l++];
if (r&1) ans += sgt[--r];
}
return ans;
}
传统的 1 开始闭区间代码：
void update(int x, int d) {
for (x += n - 1; x >= 1; x >>= 1) sgt[x] += d;
}
int query(int l, int r) {
int ans = 0;
for (l += n - 1, r += n - 1; l <= r; l >>= 1, r >>= 1) {
if (l&1) ans += sgt[l++];
if (~r&1) ans += sgt[r--];
}
return ans;
}
然后，这个东西也可以带标记（显然），甚至支持标记下传。对于单点操作，下传它的所有祖先；对于一个区间 [l,r]，下传 l 和 r 的所有祖先即可。
以上我们得到了一个非常好写且常数小的线段树。不过还可以进行一些更有意思的扩展：
我们发现这个东西没必要是二叉树：定义叉数为 b（b\ge 2），只需要将 \lfloor i/2\rfloor 改为 \lfloor i/b\rfloor，判散块的方法修改（以左端点为例：\lfloor i/2\rfloor=\lfloor (i-1)/b\rfloor 说明在一个散块中），以及处理最后的散块即可。
编号可以仍然取 [n,2n)，这肯定没问题。其实可以选择 \lfloor n/(b-1)\rfloor 为起始的左端点。
更进一步地，这个 b 甚至完全没必要是整数！我们以上的处理过程中完全未利用树结构的性质（叉数固定）。
所以稍加修改就可以获得一个任意实数叉线段树的代码：
void update(int x, int d) {
for (x += n; x; x /= b) sgt[x] += d;
}
int query(int l, int r) {
int ans = 0;
for (l += n, r += n; int(l / b) != int(r / b); l /= b, r /= b) {
while (int(l / b) == int((l - 1) / b)) ans += sgt[l++];
while (int(r / b) == int((r - 1) / b)) ans += sgt[--r];
}
return accumulate(sgt + l, sgt + r, ans);
}
```cpp
void update(int x, int d) {
for (x += n - 1; x; x /= b) sgt[x] += d;
}
int query(int l, int r) {
int ans = 0;
for (l += n - 1, r += n - 1; int(l / b) != int(r / b); l /= b, r /= b) {
while (int(l / b) == int((l - 1) / b)) ans += sgt[l++];
while (int(r / b) == int((r + 1) / b)) ans += sgt[r--];
}
return accumulate(sgt + l, sgt + r + 1, ans);
}
```
当然，为了更好的常数，可以改为乘倒数或者预处理父亲（但是这个东西本来就是娱乐向 :P）
树状数组 1 的完整通过代码（$1$ 下标闭区间，另一种写法参考原文）：
```cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 9;
constexpr double b = 2;
int n, m, sgt[N << 1];
void update(int x, int d) {
for (x += n - 1; x; x /= b) sgt[x] += d;
}
int query(int l, int r) {
int ans = 0;
for (l += n - 1, r += n - 1; int(l / b) != int(r / b); l /= b, r /= b) {
while (int(l / b) == int((l - 1) / b)) ans += sgt[l++];
while (int(r / b) == int((r + 1) / b)) ans += sgt[r--];
}
return accumulate(sgt + l, sgt + r + 1, ans);
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> sgt[i + n - 1];
for (int i = (n << 1) - 1; i >= b; --i) sgt[int(i / b)] += sgt[i];
for (int op; m; --m)
if (cin >> op; op == 1) {
int x, d;
cin >> x >> d;
update(x, d);
} else {
int l, r;
cin >> l >> r;
cout << query(l, r) << '\n';
}
return cout << flush, 0;
}
```