对于一个PC矩阵，可以用常数时间获得任意连续范围内的数字部分和
但是我们现在需要一种更好的算法 对于不连续的部分和 也能够进行预处理 争取获得多项式级别甚至常数级别的算法
于是我想到可以将原来的PC矩阵拉长 重复一些数字的排列 造成一些冗余 然后在这样的新矩阵上坐于计算 然后在部分和查询的时候争取能够在多项式级别的时间内完成
于是从一维的算起
具体地说
我现在想研究这样一个问题
我现在想研究这样一个问题
给定一个n阶完全图<V,E>
求一条v的最短序列s（当然是有重复顶点的序列）
在E中的任意一条边 都在这个序列的相邻顶点中
然后延展到n中任意k个点的组合都能包含在s的相邻k顶点中
比如说
n=4的时候 四个顶点分别是v1 v2 v3 v4
那么
序列s4 = <v3 v1 v2 v3 v4 v1 v2 v4>
那么对于这个完全图中的所有边
v1 v2
v1 v3
v1 v4
v2 v3
v2 v4
v3 v4
以及所有 三个点的组合（不排列）
v1 v2 v3
v1 v2 v4
v1 v3 v4
v2 v3 v4
都能够被这个序列的某一个连续子集覆盖
但是n比较大的情况 这样的序列如何求得呢？
求一条v的最短序列s（当然是有重复顶点的序列）
在E中的任意一条边 都在这个序列的相邻顶点中
然后延展到n中任意k个点的组合都能包含在s的相邻k顶点中
比如说
n=4的时候 四个顶点分别是v1 v2 v3 v4
那么
序列s4 = <v3 v1 v2 v3 v4 v1 v2 v4>
那么对于这个完全图中的所有边
v1 v2
v1 v3
v1 v4
v2 v3
v2 v4
v3 v4
以及所有 三个点的组合（不排列）
v1 v2 v3
v1 v2 v4
v1 v3 v4
v2 v3 v4
都能够被这个序列的某一个连续子集覆盖
但是n比较大的情况 这样的序列如何求得呢？
然而我发现 其实这个事情还可以继续下去 不一定要是线形的
可以是树形结构
只要若干相邻顶点可以覆盖全部的组合就行
比如 对于n=4
3-1-2-3
4 4 4
从三出发 就可以覆盖所有的情况
然后我得到了 对于n的递推公式
遗憾的是
Vn = 2(Vn-1)-1
解出来
Vn = 2^n-1-2^n-3+1
指数级
看来这个算法是不可行的了
不过有一个新的想法 下次再试试看
