等差数列和特殊矩阵压缩公式

等差数列和特殊矩阵压缩公式/下标计数公式的应用

ref

• 等差数列 - 维基百科，自由的百科全书 (wikipedia.org)

等差数列

递推公式

• $a_n=a_{n-1}+d;(n=2,3,...)$
  • 注意,有的时候d是一个负值
• 此外,由数列的和的定义可知:
  • $对于任何数列,总是有a_n=s_n-s_{n-1};(n=2,3,...);s_n表示前n项和$
  • 有时候会很有用,比如在推导排序不等式的时候

通项

• 相关公式和性质可以有通项公式推导

• $$\begin{gathered} a_n=a_1+(n-1)d;n=1,2,3,... \\ {a}_n=a_1+nd-d=dn+(a_1-d);(将n视为变量) \\ 那么对于任何f(x)=kx+b,都可以看做是一个等差数列的通项 \\ d=k;a_1-d=b;(a_1=b+d) \end{gathered}$$

• 相邻项的性质

  • $a_n=\frac{a_{n-1}+a_{n+1}}{2};n=2,3,...$
  • $a_n+a_m=a_q+a_p;(m+n=p+q=t常数)$

等差数列和

• $$\begin{gathered} 由通向公式a_n=a_1+(n-1)d \\ {a}_1=a_1+0d \\ {a}_2=a_1+d \\ {a}_3=a_1+2d \\ ... \\ {a}_n=a_1+(n-1)d \\ s=\sum _{i=1}^n{a}_i=\sum _{i=1}^n(a_1+(n-1)d)=a_1\sum _{i=1}^{n}1+d\sum _{i=1}^n(n-1) \\ =n{a}_1+d\frac{(n-1)+(n-2)+...+0}{2} \\ =n{a}_1+d\frac{n(n-1)}{2} \end{gathered}$$

  或者
  $$\begin{gathered} s=n\frac{(a_1+a_n)}{2} \\ 另外,对于等差数列,如果x+y=t;(t为常数) \\ 那么根据通向公式有a_x+a_y=2a_1+(t-2)d(是一个常数) \\ 当t取n+1时:a_x+a_y=2a_1+(n-1)d \\ 因此,有倒序相加是2s可得到:s=n\frac{(a_1+a_n)}{2}=n\frac{(a_x+a_{n+1-x})}{2} \end{gathered}$$

等差求和公式的应用

• $假设函数f(x)用表格法可以做如下的描述;其中i,n为常数$

• $也就是说f(x)=n-(x-1)=n+1-x$

• $可以看出f(x)是一个公差为d=-1的等差数列$

• $f(x)前i项和为s_i=i{a}_1+d\frac{i(i-1)}{2}=in+(-1)\frac{i(i-1)}{2}=\frac{1}{2}i(2n-i+1)$

  • $$\begin{gathered} 或者,如果我们写出了第i项的f(x)=n-(i-1), \\ {s}_i=\frac{1}{2}n(a_1+a_n)=\frac{1}{2}i(2n-i+1) \end{gathered}$$

• 在上三角矩阵解压缩公式中,上述$i(i)=i-1$公式取

  • $$\begin{gathered} a_{i,j}=B[k],(i⩽j,i是从1开始计数的矩阵行坐标) \\ 函数k(i,j)表示元素a_{i,j}被压缩到数组B中的那个位置(下标值) \\ 而根据压缩算法,这个值就是矩阵中,a_{i,j}前面的元素个数 \\ k(i,j)=\frac{1}{2}(i-1)(2n-i+2)+(j-i) \end{gathered}$$

数列/数组游标计数公式

问题对象

• $$设自然数序列1,2,3,4,...,p-1,\underset{共计m个元素}{\underbrace{p,...,n-1,n}};其中p<n$$
• 更一般序列形式: 序列 { a n } = ⋯   , a 1 , a 2 , a 3 , ⋯   , a p , ⋯   , a q , ⋯   ; 序列\{a_n\}=\cdots,a_1,a_2,a_3,\cdots,a_p,\cdots,a_q,\cdots; 序列{an​}=⋯,a1​,a2​,a3​,⋯,ap​,⋯,aq​,⋯;
  • $下标(inde{x}_i)体现了元素间的先后关系和相邻关系$

问题内容

• 这是一维序列区间计数公式的相关讨论

  • 主要包括:

  • 知道闭区间两端元素的序号,求区间内包含多少个元素

  • 知道区间长度和区间的一个断点序号(坐标)求另一个端点的序号

• 尽管看起来讨论这种问题有点幼稚,但是为了提高解题效率,还是值得整理的

问题变体

• 开区间容易转化为闭区间问题,下面的实例中将会看到

A指针序号差/地址增量偏移/坐标计算offset

• 这一部分是讨论由区间长度计算另一端坐标的问题

• 区间&坐标问题本质的表现之一

• **增量$\Delta =end-start$**在这个问题上是一个核心概念

  • 为了便于使用,我们也叫做序号差(坐标差)
  • 增量有正负之分
  • 序号沿着增大的方向变化的,$称为正增量\Delta >0$
  • 沿着负方向减小的方向变化的,$称为负增量\Delta <0$

• $a_1,a_2,\cdots ,a_n$

  • $a_i\underset{子串长度为\Delta =j-i}{\underbrace{a_{i+1}\cdots a_{j-1}{a}_j}}$

    • $增量区间内\Delta =j-i内的元素不包括a_i;即,仅包括[a_{i+1},a_j]$

    • 或者$\underset{负增量\Delta =i-j}{\underbrace{a_i{a}_{i+1}\cdots a_{j-1}}}{a}_j$

      • $$\begin{gathered} 由于a_i\sim a_{j-1}共有L个元素;每数一下,序号在y的基础上-1 \\ 元素:序号 \\ {a}_j:y \\ {a}_{j-1}:y-1 \\ {a}_{j-2}:y-2 \\ ⋮ \\ {a}_{i+1}:y-(L-1) \\ {a}_i:y-(L) \\ 即x=y-L \end{gathered}$$

      • $特别的,当L=1有a_i\underset{L=1}{\underbrace{a_j}}$

$$offset=L=\Delta =j-i;$$

• 结合下面的描述,$|\Delta |=|j-i|$可以理解为:

  • $元素[a_{i+1},a_j]闭区间内元素数目|\Delta |$

  • $或者理解为指针从a_i移动到a_j需要执行单步移动次数$

  • $设a_i的序号为x;a_j的序号为y;$

    • $那么y=x+\Delta ;或者x=y-\Delta$
    • $特别的\Delta =1,y=x+1;x=y-1$

• $$\begin{gathered} ★a_i+\Delta =a_{i+\Delta }; \\ 表示指向a_i的指针经过正方向偏移L次 \\ (其中每次偏移,指针从前一个元素移动到相邻的后一个元素,下标(序号)变化1) \end{gathered}$$

  • $例如,当i=1,\Delta =1时,p_1经过一次移动变为p_2$

    • $\underset{{\uparrow }_{p_1}}{a_1},\underset{{\uparrow }_{p_2}}{a_2},\cdots ,a_n$

  • 从上面的关系式可以看出,$指针从a_i移动到a_j需要执行\Delta =j-i单步移动操作★$

内存中的数组而言

• 设一个数组元素占用L=3个存储单元
  • $a_1,a_2,a_3;a_4,a_5,a_6$
  • $其中a_i表示第i个存储单元$
• $那么元素e_0占用a_1,a_2,a_3;元素e_1占用a_4,a_5,a_6$
  • $Loc(e_0)=a_1,e_0的起始地址就是a_1的地址$
  • $Loc(e_1)=a_1+1\times L=a_1+1\times 3=a_4$
  • $Loc(e_i)=Loc(e_0)+i\times L=a_1+iL=a_{1+iL}$
  • $Loc(e_j)=Loc(e_i)+(j-i)L$

B闭区间内的元素数量MatchedSize

• M a t c h e d S i z e ( i n d e x i , i n d e x j ) 表示 , 序列 { a n } 的元素 a i 到元素 a j 之间连同两端包含了多少个元素 MatchedSize(index_i,index_j)表示,序列\{a_n\}的元素a_i到元素a_j之间连同两端包含了多少个元素 MatchedSize(indexi​,indexj​)表示,序列{an​}的元素ai​到元素aj​之间连同两端包含了多少个元素

• $$\begin{gathered} |\Delta |=increment(index1,index2)=|index2-index1| \\ m(start,end)=MatchedSize(index1,index2)=|\Delta |+1=|index2-index1|+1 \end{gathered}$$

• offset&MatchedSize公式都是十分基础但是用途十分广泛的计数公式,比如

  • 活动日期的计算:$11\sim 29号共有几天?days=m(11,29)=29-11+1=19$

  • $排列数公式\left(\genfrac{}{}{0ex}{}{n}{m}\right)=n(n-1)(n-2)\cdots (n-m+1)$

    • $$\begin{gathered} 则我们有p-1=n-m(或者说(p-1)+m=n); \\ 这样,(p-1)!=(n-m)!; \\ \prod _{k=0}^{m-1}(n-k)=\frac{n!}{(n-m)!} \end{gathered}$$

  • 模式串匹配算法(朴素匹配/kmp)

  • 特殊矩阵压缩/解压公式

    • k对角矩阵,其第i行形如:

      • $$0\cdots 0,a_{i,j_1},\cdots ,a_{i,j_k},0\cdots 0$$

    • 问,$a_{i,j_k}前面的非零元素有几个$;

      • 上面的问题看似不是MatchedSize的应用场合,但其实,稍微想一下,也可以转化为MatchedSize

      • $$0\cdots 0,\underset{几个元素?}{\underbrace{a_{i,j_1},\cdots ,a_{i,j_{k-1}}}},a_{i,j_k},0\cdots 0$$

      • $m_{(1,k-1)}=j_{k-1}-j_1+1$

      • $特别的,三对角矩阵(k=3)中,第i行元素a_{i,j}前面的非零元素有几个?$

        • $j_1=i-1,j_{k-1}=j-1$
        • $elems=m(i-1,j-1)=(j-1)-(i-1)+1=j-i+1$

    • 问:$\underset{子串长度为L}{\underbrace{a_i\cdots a_{j-1}}}{a}_j$

      • $其中a_j的序号为y$
      • $那么a_i的序号x为多少?$
        • $坐标差\Delta =j-i=L$
        • $\underset{子串长度为L+1}{\underbrace{a_i{a}_{i+1}\cdots a_{j-1}{a}_j}}$
          • $L+1=y-x+1即:x=y-L$
        • $a_i\underset{子串长度为L}{\underbrace{a_{i+1}\cdots a_{j-1}{a}_j}}$
          • $x=y-L$

😎小结

• 从一维序列的计数公式&坐标公式的各种形式上看

• $关系式|j-i|=|\Delta (L)|足以解决所有相关问题(以坐标差\Delta 为核心)$

  • $$\begin{gathered} 坐标差=增量长度 \\ j-i=\Delta =L_{[a_i,a_{j-1}]}=L_{[a_j,a_{i+1}]}⩾0 \\ (i-j=-\Delta )\text{\hspace{1em}(core)} \end{gathered}$$

    $$L_{[a_i,a_j]}=|\Delta |+1=|j-i|+1$$

  • $将坐标差\Delta 用闭区间距离L或(L\pm 1)表示出来$

  • $L通常是a_i\sim a_j闭区间内的元素数量,这时候\Delta (L)=L-1$

利用上面的关系式列等式,$所有关于i,j,L的值都可以一步计算的时间内得出$

公式中都具有坐标差(假设i

• $闭区间元素数量L=\Delta +1=j-i+1$
• $闭区间左端点坐标i可以由:i=j-\Delta =j-L+1;$
• $右端点坐标j=i+\Delta =i+L-1$

数组元素位置&起始地址

二维数组(矩阵)

• 按行优先排列
• $m,n分别表示矩阵的行数和列数$
  • $i\in [0,m-1]是行下标的维界$
  • $j\in [0,n-1]是列下标的维界$
• $a_{i,j}表示矩阵中的第i行第j列元素$
  • 例如,$第一个元素坐标为a_{00}$
• $L表示数组中的元素占的存储单元数,比如字节数$
• $Loc(a_{i,j})表示元素a_{i,j}在内存中的起始地址$

一维数组

• 按行优先排列

• $m分别表示一维数组的维数$

  • $i\in [0,m-1]是行下标的维界$

• $a_i表示数组中下标为i的元素$

  • 例如,$第一个元素坐标为a_0$

• $L表示数组中的元素占的存储单元数,比如字节数$

• $Loc(a_i)表示元素a_i在内存中的起始地址$

  • a[0]	a[1]	a[2]	…	a[i]

  • $$\begin{gathered} Loc(a_1)=Loc(a_0)+1\times L \\ 一种不太准确的Loc(a_i)的理解: \\ \underset{\underset{L}{\upharpoonleft }}{}\stackrel{i个元素}{\overbrace{a[0],\underset{i-1}{\underbrace{a[1],\cdots ,a[i-1]}}}},\underset{\upharpoonleft }{}a[i],\cdots \\ 比较合适的理解Loc(a_i): \\ \stackrel{i个元素}{\overbrace{\underset{{\upharpoonleft }_{Loc}}{a[0]},\underset{i-1}{\underbrace{a[1],\cdots ,a[i-1]}}}},a[i],\cdots \\ 所以:Loc(a_i)=Loc(a_0)+i\times L \end{gathered}$$

• $$Loc(a_i)=Loc(a_0)+i\times L$$

• $$\begin{gathered} Loc(a_{i,j})=Loc(a_{0,0})+i\times sizeof(row)+j\times L \\ sizeof(raw)=m\times L \\ Loc(a_{i,j})=Loc(a_{0,0})+(i\times m+j)\times L \end{gathered}$$

三角矩阵的压缩

• 三角矩阵(方阵)$A[\mathrm{1...}n][\mathrm{1...}n]$,包括
  • 上三角矩阵(下三角所有元为同一个常量)$j⩽i$
  • 下三角矩阵(上三角所有元素为同一个常量)$i⩽j$
• $上下三角包含\frac{n(n+1)}{2}个元素;在加上(占据矩阵其余位置的)一个常量c$
• $所以需要一个大小\underline{至少}为\frac{n(n+1)}{2}+1维的数组来保存必要元素$
  • $A_{三角}[1,...,n][1,...,n];B[\mathrm{1...}\frac{1}{2}n(n+1)+1]$

上三角

按行优先

• $$\begin{gathered} 从矩阵的第一个元素a_{0,0}开始,按行扫描,一直到a_{i,j}, \\ 期间遇到的属于上三角(a_{i,j};i⩽j)的元素的个数: \end{gathered}$$

  第x行	行x上属于上三角的元素的个数
  1	$n$
  2	n-1
  3	$n-2$
  …	…
  $x$	$n-(x-1)$
  $i-1(x=i-1时)$	$n-(i-1-1)=n-i+2$
  i(特别的)	$j-i+1$

  • $$\begin{gathered} 如果B[\mathrm{0...}],那么k_0=S_{i-1}+s_i-1; \\ {S}_{i-1}=\frac{(i-1)(2n-i+2)}{2}是前i-1行的元素总数量, \\ {s}_i=j-i+1是第i行的a_{i,i}到a_{i,j}的元素数量 \\ {k}_0=\frac{(i-1)(2n-i+2)}{2}+(j-i+1)-1=\frac{(i-1)(2n-i+2)}{2}+j-i \end{gathered}$$

  • $$\begin{gathered} 如果B[\mathrm{1...}],那么k_1=S_{i-1}+s_i; \\ {k}_1=\frac{(i-1)(2n-i+2)}{2}+j-i+1 \end{gathered}$$

映射公式用法

$$\begin{gathered} k_0(i,j)=\{\begin{array}{l}\frac{(i-1)(2n-i+2)}{2}+j-i;(i⩽j)\\ \frac{n(n+1)}{2};(j<i)\end{array} \\ 即A[i][j]=B[k(i,j)] \\ k根据B数组的要求而决定选用k_0还是k_1;实际上更多的用的前者 \end{gathered}$$

按列优先

• $$k_1(i,j)=\frac{1}{2}j(j-1)+i$$

下三角矩阵

• 和上三角十分相似的讨论过程
• 压缩过程行列情况对调(按行优先/按列优先)
• 本质上是等差数列求和公式的应用

😀公式使用条件

$k_0\&k_1的关系$

• 经过前面的讨论,$可以知道k_0=k_1-1;或者k_1=k_0+1$
• $之后我们仅讨论k_0或者k_1$

$A[\mathrm{0...}]vsA[\mathrm{1...}]$

• 有时,$矩阵的坐标是从0开始的:i\in [0,n],j\in [0,n]$
• $前的公式都是在i\in [1,n],j\in [1,n]情况下推导的$
• $如果要求用a_{i,j};i\in [0,n],j\in [0,n]来计算k,那么必须要一定的调整$
• 幸运的是,这个调整比较简单,$只需要将a_{i,j}直接映射a_{i+1,j+1}就可以了$

对称矩阵

• 对称矩阵和三角矩阵十分相近

• 不同的是对称矩阵的特点:$a_{i,j}=a_{j,i}$

• $$\begin{gathered} 这意味着,如果对称矩阵将上三角(i⩽j)压缩到数组B中, \\ 并且要求的是a_{p,q}(p⩾q)的压缩位置,那么可以利用公式a_{q,p}=a_{p,q}来解压 \end{gathered}$$

  $$k_0(i,j)=\{\begin{array}{l}\frac{i(i-1)}{2}+j-1;i⩾j\\ \frac{j(j-1)}{2}+i-1;i⩽j\end{array}$$

三对角矩阵

• 对角阵/三对角矩阵均为方阵
  • $记为A_{n\times n}$
  • $二维数组形式A[1,...,n][1,...,n]$

• $第1行到i-1行每行多有三个元素(补上的虚拟元素Q_{-1}后面再-1,则s_{i-1}=3(i-1)-1)$

• $第i行有b_i=j-(i-1)个元素$

  • 因为,三对角矩阵的斜对角区域的每一行的三个元素可以表示为:$a_{i,i-1},a_{i,i},a_{i,i+1}$

  • 这时
    $$j=\{\begin{array}{l}i-1\\ i\\ i+1\end{array}$$

压缩公式

• $将矩阵A[1,...,n][1,...,n]中的元素a_{i,j}压缩到B数组中的下标为k=k(i,j)的位置$

  • $计算k的原理是,计算a_{i,j}前面的元素个数:k_{before}(i,j)=3(i-1)-1+j-(i-1)=2i+j-3$

  • $B[0,...,n-1],从B[0]开始存放元素a_{0,0},..$
    $$k_0(i,j)=3(i-1)-1+j-(i-1)=2i+j-3$$

• $B[1,...,n],从B[1]开始存放元素a_{0,0},...$

  这种情况也是有的(比如,我们用B[0]保存其他元信息,比如长度)
  $$k_1(i,j)=k_0(i,j)+1=2i+j-2$$

确定数组中的元素解压后的行/列公式

• 按行优先

确定行

$$\begin{gathered} i(k)=\lfloor \frac{k+1}{3}+1\rfloor =\lfloor \frac{k+1}{3}\rfloor +1 \\ =\lfloor \frac{k+4}{3}\rfloor \end{gathered}$$

• 例如

  • $$\begin{gathered} i(0)=1 \\ i(1)=1 \\ i(2)=2 \\ ⋮ \end{gathered}$$

我们来推导一下

$$\begin{gathered} i=1;k=\{\begin{array}{l}(-1)(虚拟)\\ 0\\ 1\end{array} \\ i=2;k=\{\begin{array}{l}2\\ 3\\ 4\end{array} \\ i=3;k=\{\begin{array}{l}5\\ 6\\ 7\end{array} \\ ⋮ \\ i=i;k=\{\begin{array}{l}3(i-1)-1\\ 3(i-1)\\ 3(i-1)+1\end{array} \\ k+1=\{\begin{array}{l}3(i-1)\\ 3(i-1)+1\\ 3(i-1)+2\end{array} \\ \frac{k+1}{3}=\{\begin{array}{l}(i-1)\\ (i-1)+\frac{1}{3}\\ (i-1)+\frac{2}{3}\end{array} \\ \frac{k+1}{3}+1=\{\begin{array}{l}i\\ i+\frac{1}{3}\\ i+\frac{2}{3}\end{array} \\ 可见:上式子两边同时向下取整,就得到k映射到i的函数 \\ \lfloor \frac{k+1}{3}+1\rfloor =\lfloor \frac{k+1}{3}\rfloor +1=i \\ i(k)=\lfloor \frac{k+1}{3}+1\rfloor =\lfloor \frac{k+1}{3}\rfloor +1 \end{gathered}$$

确定列

• $$\begin{gathered} j(k,i)=k-2i+3;又因为i=i(k)=\lfloor \frac{k+1}{3}+1\rfloor \\ 或者 \\ j(k)=j(k,i(k))=k-2(\lfloor \frac{k+1}{3}+1\rfloor )+3 \end{gathered}$$