Fenwick Tree with Linear Algebra

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
10	nor	152

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 $$$

For example, with $$$n=10$$$, we have

$$$ T = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix}. $$$

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$$$

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 respect to $$$t$$$ that the induction statement is true for all $$$m < 2^t$$$. For any $$$t\geq 1$$$ and $$$0 \leq m <2^t$$$, set $$$n=2^t$$$, and using the induction result with $$$m \leq 2^t$$$ we have

$$$ T_{n+m} = \begin{pmatrix} T_n & O_{n\times m} \\ O_{m\times n} & T_m \\ \end{pmatrix} $$$

Thus

$$$ T_{n+m}^{t+1} = \begin{pmatrix} T_n - & O_{n\times m} \\ O_{m\times n} & T_m \\ \end{pmatrix} $$$

Rev.	Кто	Когда	Δ	Комментарий
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

История