澹台千儿

# 概述 线段树 (segment tree) 是用来维护区间信息的数据结构，可以参考板子题【模板】线段树 1、【模板】线段树 2 及【模板】线段树 3。以上三题中，前者是后者的子集。下面，我们以区间和作为例子进行讨论。 线段树的想法是通过将长度大于 1 的区间划分成两个区间进行递归维护。这样，就可以形成一个树形结构，我们称之为线段树。对每次修改，我们需要修改 O(log⁡n)O(\log n)O(logn) 级别节点的值。对每一次区间信息检索，我们需要查询 2log⁡n2\log n2logn 级别节点的值。 #...

# 第三章 系统总线 总线 (bus) 是一组能为多个部件分时共享公共信息的传送线路。总线的两个重要特点是分时和共享。 # 总线的分类 根据总线的数据传输形式，可以分为并行传输总线和串行传输总线。根据连接部件的不同，可以分为片内总线、系统总线和通信总线。片内总线是芯片内部的总线，例如在 CPU 内部或寄存器之间的总线。系统总线是连接 CPU、主存和 IO 设备的总线，又称板级总线。根据系统总线传输信息的不同，又可以分为数据总线、地址总线和控制总线。通信总线是连接各计算机的总线，例如光纤等。我们讨论的重点是系统总线。 # 总线结构 # 总线的性能指标 # 总线控制 总线控制是 #...

# 群作用 # 定义 我们定义群 GGG 对一个集合 SSS 的作用 (action) 是一个 (⋅,⋅):G×S→S(\cdot, \cdot):G \times S \to S(⋅,⋅):G×S→S 的映射。对 g∈Gg \in Gg∈G 及 s∈Ss \in Ss∈S, 我们记其映射为 (g,s)→gs(g,s) \to gs(g,s)→gs. 该映射需要满足下列两个要求： ∀s∈S, 1s=s\forall s \in S,\,1s=s∀s∈S,1s=s; ∀g1,g2∈G,s∈S, (g1g2)s=g1(g2s)\forall g_1,g_2 \in G, s \in...