- $1 = 2^0 \times 1 = (0, 1]$ (Subtract $2^0 = 1$)
- $2 = 2\times 1 = (0, 2]$ (Subtract $2^1 = 2$)
- $3 = 3 = (2, 3]$
- $4 = 2^2 = (0, 4]$
- $5 = 5 = (4, 5]$
- $6 = 2\times 3 = (4, 6]$
- $7 = 7 = (6,7]$
- $8 = 2^3 = (0,8]$
- $9 = 9 = (8, 9]$
- $10 = 2\times 5 = (8, 10]$
- $11 = 11 = (10, 11]$
- $12 = 2^2\times 3 = (8, 12]$
- $13 = 13 = (12, 13]$
- $14 = 2\times 7 = (12, 14]$
- $15 = 15 = (14, 15]$
- $16 = 2^4 = (0, 16]$

- $a[15] = (14, 15], a[14] = (12, 14], a[12] = (8, 12], a[8] = (0, 8]$.

- $15=2^0 \cdot 15 \xrightarrow{-2^0} 14=2^1 \cdot 7 \xrightarrow{-2^1} 12=2^2\cdot3 \xrightarrow{-2^2} 8=2^3\cdot1 \xrightarrow{-2^3} 0$

$\begin{aligned}
&-a = \lnot a + 1 = x01^r + 1 = \overline{x}10^r \\
&a \& (-a) = a \& (\lnot a + 1) = (x 10^r) \& (\overline{x}10^r) = 0^{|\alpha|}10^r = 2^r
\end{aligned}$

$a - (a \& (-a)) = \langle x 1 0^r \rangle - \langle 1 0^r \rangle = \langle x 0 0^r \rangle$

That is, we successfully strip off the trailing $1$.
Armed with the theory, our implemtation becomes:
```
#define LSB(x) x&(-x)
int a[N];
int q(int i) {
int s = 0;
while (i > 0) {
s += a[i];
i -= LSB(i); // strip off trailing 1.
}
return s;
}
```

- $a[9] = (8, 9], a[10] = (8, 10], a[12] = (8, 12], a[16] = (0, 16]$.

- $9=2^0 \cdot 9 \xrightarrow{+2^0} 10=2^1 \cdot 5 \xrightarrow{+2^1} 12=2^2\cdot3 \xrightarrow{+2^2} 16=2^4\cdot1 \xrightarrow{+2^4} \dots$

```
#define LSB(x) x&(-x)
int tree[N];
int u(int i, int v) {
while (i < N) { tree[i] += v; i += LSB(i); }
}
```

- $Query(i) = \sum_i d[Q^i(q)]$

- $Update(i, val) = \forall j~, d[U^j(i)]~\texttt{+=}~ val$

- $q \geq u \iff \left\vert \{ Q^i(q)~:~ i \in \mathbb{N} \} \cap \{ U^i(u)~:~i \in \mathbb{N} \} \right\vert = 1$

- $Q(i=2^r\cdot a) = i - 2^r = 2^r(a-1)$
- $U(j=2^s\cdot b) = j + 2^{s} = 2^{s}(b+1)$

```
# calculate orbits of query and update in fenwick tree
def lsb(i): return i & (-i)
def U(i): return i + lsb(i)
def Q(i): return i - lsb(i)
def orbit(f, i):
s = set()
while i not in s and i > 0 and i < 64:
s.add(i); i = f(i)
return s
if __name__ == "__main__":
for q in range(1, 16):
for u in range(1, 16):
qo = orbit(Q, q); uo = orbit(U, u)
c = qo.intersection(uo)
print("q:%4s | u:%4s | qo: %20s | uo: %20s | qu: %4s" %
(q, u, qo, uo, c))
print("--")
```