设A是一个nxn二进制矩阵，其行的形式为0^k 1^l 0^m或1^k 0^l 1^m。此外，A沿对角线有零。维度 n 最多可以达到10^5。矩阵将通过给出1块开始和结束的索引来给出。
换句话说，这些行是被0包围的1的运行或被1包围的0的运行。一行可以全为零，但不能全为零(对角线上为零(。
一个例子A：
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 0, 0]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0, 1, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 1, 1, 0, 0, 0, 0]
如何有效地计算A^2的痕迹(在O(n^2)时间内(？
这等价于找到 A 的特征多项式的(n-2)'nd 系数，将其表示为g_2(A)，因为
tr(A^2) = (tr A)^2 - 2g_2(A) = -2g_2(A)
这个问题来自哪里：
我们得到一个数字 [1..n] 的排列 p，并且对数量感兴趣
r(p) = #{k | p^{-1}[k+1] < p^{-1}[k]}
这里的p^{-1}[k]是指p中k的指数。我们要计算两个将 r 减少 2 的元素的所有交换。这可以通过考虑每个指数kp[k]有利可图来实现。这取决于p[k]-1和p[k]+1的位置(仅在边缘情况下的其他位置(，这就是行形式的来源。但是另一个元素的移动也应该是有利可图的，因此问题变成了矩阵中有多少元素AA[i][j]和A[j][i]等于1，我们被引导计算A^2的痕迹。此外，在原始问题中，我们想从中减去相邻数(|p[i]-p[j]|==1)的对，因为这不会r减少 2，而只会减少 1。但这可以在线性时间内完成，为了简单起见，这个问题不考虑。虽然，可能是原始问题对矩阵A施加了一些进一步的限制，这些限制可能有助于计算(？
这可以在O(n log n(时间内使用使用芬威克树的扫描线算法完成。
该算法按顺序计算产品对角线的条目。它维护一个保存当前列的芬威克树。泛伟树可以在时间 O(log n( 中更新条目，并在时间 O(log n( 中报告子数组总和。对于位置 {i} × {j...j'-1} 中的每一部分行，我们创建两个事件，(j， i， +1( 和 (j'， i， -1(。按事件的第一个条目(列，也称为时间(对事件进行排序和分组。事件 (j， i， Δ( 表示在时间 j 处，将条目 i 递增 Δ。要计算对角元素索引 k，首先应用具有时间 k 的所有事件，然后报告相应行中 1 的所有间隔，并将它们相加。