Fenwick Tree with Linear Algebra

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Hello everyone!

While I am solving this problem 1967C - Fenwick Tree, I read Elegia matrix solution and finally came up with my own solution that is based on his approach, using the matrix of linear transformation. Throughout the solution is tons of "heavy-math" knowledges and assumptions that is considered to be hard to see. Motivated enough, I have my heart set on writing an entire blog here with an ambition to prove every details in my solution.

Let's first quote the problem here

Problem Statement

Let $$$\operatorname{lowbit}(x)$$$ denote the value of the lowest binary bit of $$$x$$$, e.g. $$$\operatorname{lowbit}(12)=4, \operatorname{lowbit}(8)=8.$$$

For an array $$$a$$$ of length $$$n$$$, if an array $$$s$$$ of length $$$n$$$ satisfies $$$s_k=\left(\sum\limits_{i=k-\operatorname{lowbit}(k)+1}^{k}a_i\right)\bmod 998\,244\,353$$$ for all $$$k$$$, then $$$s$$$ is called the Fenwick Tree of $$$a$$$. Let's denote it as $$$s=f(a).$$$

For a positive integer $$$k$$$ and an array $$$a$$$, $$$f_k(a)$$$ is defined as follows:

$$$ f^k(a)= \begin{cases} f(a)&\textrm{if }k=1\\ f(f^{k-1}(a))&\textrm{otherwise.}\\ \end{cases} $$$

You are given an array $$$b$$$ of length $$$n$$$ and a positive integer $$$k$$$. Find an array $$$a$$$ that satisfies $$$0\leq a_i <998244353$$$ and $$$f_k(a)=b$$$. It can be proved that an answer always exists. If there are multiple possible answers, you may print any of them.

Solution

The definition of $$$s_k$$$ makes us think of the linear map $$$T: \mathbb{R_n}\rightarrow \mathbb{R_n}$$$ which map a vetor array $$$a$$$ to the Fenwick Tree of $$$a$$$, in other words $$$T(a)=f(a)$$$. Note that $$$R_n$$$ here is the set of all matrices with size $$$n\times 1$$$ and if $$$a \in \mathbb{R_n}$$$ then

$$$ a = \begin{pmatrix} a_1 \\ a_2 \\ \vdots \\ a_n \end{pmatrix}. $$$

From the definition of $$$s_k$$$ we can see that the matrix $$$T$$$ of the linear map is

$$$ T = (t_{ij})_{1\leq i, j \leq n} $$$

and satisfy

$$$ t_{ij}= \begin{cases} 1&\textrm{if } i-\operatorname{lowbit}(i)+1\leq j\leq i\\ 0&\textrm{otherwise.}\\ \end{cases},\forall 1\leq i, j \leq n $$$

Example

Because $$$T$$$ is an lower triangular matrix, we have $$$\det T = 1$$$ for all $$$n\geq 1$$$ and the characteristicpolynomial of $$$T-I$$$ is

$$$ \det(T-I-\lambda I) = (-\lambda)^n. $$$

So all the eigenvalues of $$$T-I$$$ are $$$0$$$, $$$T-I$$$ is nilpotent and according to the Cayley-Hamilton theorem, we have

$$$ (T-I)^n=0. $$$

However,all of these above observations are just not enough to solve this problem, as will be seen later on. Indeed, we need to find the smallest integer $$$m$$$ such that

$$$ (T-I)^m=0. $$$

We claim that $$$m = \lfloor\log_2(n) \rfloor +1$$$.

Warning: the solution requires many advanced mathematical techniques and ... long, but it's the best way I can think of.

Proof of m (using block matrix and induction)

Denote $$$T_n$$$ to be the linear transformation matrix with size $$$n$$$. First, we will prove that $$$m = \lfloor\log_2(n) \rfloor +1$$$ for all $$$n=2^t (t\geq 1)$$$. We will prove this by induction on $$$t$$$.

With $$$t=1$$$ or $$$n=2$$$, we can see that

$$$ T_2 - I_2 = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}. $$$

And

$$$ (T_2 - I_2)^2 = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}. $$$

So $$$k=2=\lfloor\log_2(2) \rfloor +1$$$

Suppose we have $$$t=m$$$ is true with $$$m\geq 1$$$, set $$$n = 2^m$$$. We will prove that $$$t=m+1$$$ is also true, or $$$2n=2^{m+1}$$$ is true.

By induction, because $$$\lfloor\log_2(2^{m}) \rfloor +1 = m + 1$$$, so we have

$$$ (T_n-I_n)^m \neq O_n \text{ and } (T_n-I_n)^{m+1} = O_n. $$$

Here $$$O_n$$$ denotes the $$$n\times n$$$ matrix with all entries equal zero. We need to prove that

$$$ (T_{2n}-I_{2n})^{m+1} \neq O_{2n} \text{ and } (T_{2n}-I_{2n})^{m+2} = O_{2n}. $$$

Observer from small cases, we can see that with $$$n$$$ of the form $$$2^t$$$ then

$$$ T_{2n} = \begin{pmatrix} T_n & O_n \\ B_n & T_n \end{pmatrix} $$$

With

$$$ B_n = \begin{pmatrix} 0 & 0 & \ldots & 0 \\ 0 & 0 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \ldots & 1 \\ \end{pmatrix} \in \mathbb{M_{n\times n}(\mathbb{R})}. $$$

For the sake of brevity, I will exclude the proof of $$$B_n, T_{2n}$$$ having the aforementioned forms. Since $$$T_n-I$$$ has the $$$n$$$-th column with all entries being zero, we have $$$(T_n-I_n)B_n = O_n$$$. So, performing block matrix multiplication, we have

$$$ (T_{2n} - I_{2n})^{2} = \begin{pmatrix} (T_n-I_n)^{2} & O_n \\ B_n(T_n-I_n) +(T_n-I_n)B_n & (T_n - I_n)^{2} \end{pmatrix} = \begin{pmatrix} (T_n-I_n)^{2} & O_n \\ B_n(T_n-I_n) & (T_n - I_n)^{2} \end{pmatrix}. $$$

Generally we have

$$$ (T_{2n} - I_{2n})^{m+1} = \begin{pmatrix} (T_n-I_n)^{m+1} & O_n \\ B_n(T_n-I_n)^m & (T_n - I_n)^{m+1} \end{pmatrix} = \begin{pmatrix} O_n & O_n \\ B_n(T_n-I_n)^m & O_n \end{pmatrix} $$$

To prove $$$B_n(T_n-I_n)^m \neq O_n$$$, observe that since $$$T_n-I_n$$$ matrix have all nonegative entries, so does $$$(T_n-I_n)^{m}$$$. On the other hand if there exists matrix $$$X$$$ such that $$$B_nX = O_n$$$ then $$$X$$$ must have the sum of every column equal zero.

Since $$$(T_n-I_n)^{m}$$$ have only nonegative entries and $$$(T_n-I_n)^{m}\neq O_n$$$ then it must have at least one column with positive sum. Hence, $$$B_n(T_n-I_n)^m \neq O_n$$$. So $$$(T_{2n} - I_{2n})^{m+1}\neq O_{2n}$$$. Finally

$$$ (T_{2n} - I_{2n})^{m+2} = \begin{pmatrix} (T_n-I_n)^{m+2} & O_n \\ B_n(T_n-I_n)^{m+1} & (T_n - I_n)^{m+2} \end{pmatrix} = \begin{pmatrix} O_n & O_n \\ O_n & O_n \end{pmatrix} = O_{2n}. $$$

Induction complete. So far, we have prove $$$m = \lfloor\log_2(n) \rfloor +1$$$ for all $$$n = 2^t$$$. The remaining part is easy, we will once again use induction with $$$2^{t-1}\leq n < 2^t$$$, we then have $$$m = t$$$.

The case $$$n<2^1$$$ is trivial
Suppose $$$n< 2^t$$$ is true for $$$t\geq 1$$$, we will prove $$$2^{t}\leq n<2^{t+1}$$$ with $$$m=t+1$$$ is also true. For any $$$0 \leq k <2^t$$$, set $$$n=2^t$$$, and using the induction result with $$$k \leq 2^t$$$ we have

$$$ (T_k-I_k)^{t} = O_k. $$$

On the other hand, since $$$n=2^t$$$, we have

$$$ (T_n-I_n)^{t} \neq O_n \text{ and } (T_n-I_n)^{t+1} = O_n. $$$ $$$ T_{n+k} = \begin{pmatrix} T_n & O_{n\times k} \\ O_{k\times n} & T_k \\ \end{pmatrix} $$$

Thus

$$$ (T_{n+k}- I_{n+k})^{t} = \begin{pmatrix} (T_n-I_n)^{t} & O_{n\times k} \\ O_{k\times n} & (T_k-I_k)^{t} \\ \end{pmatrix} = \begin{pmatrix} (T_n-I_n)^{t} & O_{n\times k} \\ O_{k\times n} & O_k \\ \end{pmatrix} \neq O_{n+k}. $$$

And

$$$ (T_{n+k}- I_{n+k})^{t+1} = \begin{pmatrix} (T_n-I_n)^{t+1} & O_{n\times k} \\ O_{k\times n} & (T_k-I_k)^{t+1} \\ \end{pmatrix} = \begin{pmatrix} O_n & O_{n\times k} \\ O_{k\times n} & O_m \\ \end{pmatrix} = O_{k+n}. $$$

Induction complete. So for all $$$n\geq 1$$$ we have $$$m=\lfloor\log_2(n) \rfloor +1$$$, as desired.

It's not the end, I am still writing and updating this topic.

Rev.	By	When	Δ	Comment
en11	dangcaominh	2024-09-20 13:28:41	69
en10	dangcaominh	2024-05-08 10:09:21	2527	(published)
en9	dangcaominh	2024-05-08 09:44:06	3162	(saved to drafts)
en8	dangcaominh	2024-05-07 18:26:44	1	(published)
en7	dangcaominh	2024-05-07 18:26:15	72
en6	dangcaominh	2024-05-07 18:23:10	1658
en5	dangcaominh	2024-05-07 17:20:50	1725
en4	dangcaominh	2024-05-07 16:32:39	1499
en3	dangcaominh	2024-05-07 13:28:08	664
en2	dangcaominh	2024-05-07 12:35:11	2483	Tiny change: 'lem:1967C] , I read [' -> 'lem:1967C], I read ['
en1	dangcaominh	2024-05-07 09:29:16	60	Initial revision (saved to drafts)

Problem Statement

Solution

History