拟阵（matroid）是一个二元组 \(M=(S,I)\)，其中 \(I\) 是一个定义在 \(S\) 子集上的一个集族，称之为独立集，在独立集中的子集称之为独立的
需满足性质：
遗传性：\(A\subset B,B\in I\Rightarrow A\in I\)。
扩充性（交换性）：\(\exists A,B\in I,|A|>|B|\Rightarrow \exists i\in A/B,(B\cup{i})\in I\)。
有扩充性可以直接得到独立集的最大大小是一定的。
顾名思义，matroid 这个单词好像跟线性代数有点关系。事实上用拟阵最初就是用来研究“线性无关”这一个性质的。假设有若干条向量，那么称这些向量的一个子集是独立的当且仅当它们线性无关。根据线性代数知识我们容易证明它满足上述两条性质。这里我们在 \(\mathbb F_2\) 域（也就是异或意义下）下研究“线性无关”，所谓的独立集就是我们讲的线性基。
另一个关于拟阵的应用是研究“无环”这一个性质。对于图的边集，若这个边集不形成环那么称其是独立的。类似矩阵树定理，我们发现，如果对每一条边建立一个点数维的向量，其中该边一个端点代表的维度的值是 \(-1\)，另一个值是 \(1\)，其它维度都是零。那么研究无环这个性质就相当于研究“线性无关”。
我们可以这样定义拟阵中的环：一个去掉任意一个元素都会使其独立的非独立集。这样拟阵中的环就是一种图论中的环的抽象了。线性基中，所谓的环路就是一堆异或和为 \(0\) 且没有真子集异或和为 \(0\) 的一个集合。
拟阵的一个大应用就是证明贪心问题。我们对 \(S\) 中的每一个元素赋权，那么我们想要找出权值和最大的独立集。如果该抽象结构是拟阵的话，那么我们就可以 "Kruskal" 求出最优解：按权值从大到小排序，能加就加。
算导上有证明，此处不叙。我们这里要思考的是这个结论意味这什么？
这意味着在拟阵结构中，我们得到的最优解不仅仅是和最大的，而且也是把独立集权值从大到小排序后字典序最大的。
意味着最大权线性基有一种简单的求法：直接贪心。
然而这还不够！我们要发掘线性基问题与生成树问题的相似性。
我们考虑如果生成树问题强制在线了，那我们会怎么做？假设新加入一条边 \((u,v)\)，我们会找到生成树上是否包含 \((u,v)\) 这条路径，如果有，那么就在新形成的简单环上扣掉最小的那条边。
这个事实对于线性基同理！我们同样只需要找到当前的“生成树”，也就是所谓的线性基，是否能够表出你插入的数 \(x\)，如果不行，那么就在包含 \(x\) 的环路（此处讲的是拟阵意义下的环路了！）中删去权值最小的了！
具体到实现，可以真的找出所谓的环路，也可以每次只需要比较当前插入的数与线性基中的数的权值，如果大于那么就把这个值 swap 出来继续向下插入。这样的复杂度跟普通的插入一模一样！
这样我们就实现了一个强大的动态维护最大权线性基的算法。我们可以用它来实现离线带插带删的线性基。
具体地，我们找出每个点的被删除的时间，然后按照插入时间排序依次插入，查询的时候直接忽略删除掉的元素。
这样为什么是对的呢？因为最大权线性基同时也是“最大字典序”的，所以这样保留下来的无论如何也是对后面最有用的元素！
这样复杂度甚至做到了跟只有插入同级别！