主席树
主席树又名可持久化线段树 简介传统意义上的主席树就是可持久化线段树，什么叫可持久化呢？就是这棵树啊，可以记录每一次修改的内容，换句话说，就是可以访问这棵树的历史记录。 常见应用 区间/树上路径第 K 大 区间不同数的个数 很多问题如果用线段树处理的话需要采用离线思想，若用主席树则可直接在线处理。故很多时候离线线段树求解可以转化为在线主席树求解。 注意，主席树本质就是线段树，变化就在其实现可持久化，后一刻可以参考前一刻的状态，二者共同部分很多。一颗线段树的节点维护的是当前节点对应区间的信息，倘若每次区间都不一样，就会给处理带来一些困难。有时可以直接细分区间然后合并，此种情况线段树可以直接搞定；但有时无法通过直接划分区间来求解，如频繁询问区间第k小元素，当然，此问题有比较特殊的数据结构-划分树。其实还有一个叫做归并树，是根据归并排序实现的，每个节点保存的是该区间归并排序后的序列，因此，时间、空间复杂度都及其高，...
SQL中的EXISTS
SQL中的EXISTS与SQL中的NOT EXISTS 从SQL中基础的WHERE字句开始有一学生信息表 1SELECT Sno, Sname FROM Student WHERE Sdept = 'IS'; 很显然，在执行这条 SQL语句的时候，DBMS会扫描 Student表中的每一条记录，然后把符合 Sdept = 'IS'这个条件的所有记录筛选出来，并放到结果集里面去。也就是说 WHERE关键字的作用就是判断后面的逻辑表达式的值是否为 True。如果为 True，则将当前这条记录（经过SELECT关键字处理后）放到结果集里面去，如果逻辑表达式的值为 False则不放。 使用EXISTS关键字123SELECT Sname FROM Student WHERE EXISTS (SELECT * FROM SC WHERE Sno = Student.Sno AND Cno = '1'); 这条SQL语句的作用，就是查找所有选修了 1...
Java虚拟机笔记-字节码文件中的常量池
常量池（Constant Pool） 常量池（Constant Pool）12345678910111213package indi.greenhat.bytecode;public class Test1 { private int a = 1; public int getA() { return a; } public void setA(int a) { this.a = a; }} 123456789101112131415161718192021222324Constant pool: #1 = Methodref #4.#20 // java/lang/Object."<init>":()V #2 = Fieldref #3.#21 // indi/greenhat/bytecode/Test1.a:I #3 = Class ...
莫队算法
莫队算法 简述莫队算法使用分块的思想，可以解决一类离线区间询问问题 莫队算法（mo's algorithm）一般分为两类，一是莫队维护区间答案，二是维护区间内的数据结构。当然也有树上莫队，带修改莫队、二维莫队等等 普通莫队莫队的精髓就在于，离线得到了一堆需要处理的区间后，合理的安排这些区间计算的次序以得到一个较优的复杂度。 我们考虑一个问题，给一个序列，m次询问，每次询问你区间$[l,r]$有多少种不同的颜色。 $n,m\leq 100000n,m≤100000$ 先考虑暴力，对每次询问遍历一遍 $[l,r]$，这样是$O(nm)$的 换种方式暴力，定义ql和qr，表示区间 $[ql,qr]$内有多少颜色，再定义cnt数组， 表示第i种颜色在区间 $[ql,qr]$出现了多少次。那么现在的情况就是已经 $[ql,qr]$的答案，需要我们去转移求$[l,r]$区间的答案 因为这个是莫队算法的基础，所以模拟一下这个过程： 我们的初始在这个状态，假设蓝色为1，红色为2，绿色为3，区间$[ql,qr]$有 那么$cnt_1=3, cnt_2=3,...
Java虚拟机笔记-字节码格式
.class文件 Java从刚开始的时候就有两套...
Java虚拟机笔记-JDBC驱动加载机制
通过JDBC驱动加载理解线程上下文加载器 JDBCJDBC提供了独立于数据库的统一API，MySQL，Oracle等数据库公司都可以基于这个标准接口来进行开发。包括java .sql包下的Driver，Connection，Statement，ResultSet是JDBC提供的接口。而DriverManager是用于管理JDBC驱动的服务类，主要用于获取Connection对象（此类中全是静态方法） 下面是一个简单的jdbc连接数据库过程。重点不在能不能连接，而是其加载过程。 12345678910111213package Test;import java.sql.Connection;import java.sql.DriverManager;public class Test { public static void main(String[] args) throws Exception { Class.forName("com.mysql.cj.jdbc.Driver"); String...
Mysql外键与级联操作
外键与级联更新删除 之前没用过外键与级联更新，所以总结一下，用的数据库版本： mysql Ver 8.0.15 for linux-glibc2.12 on x86_64 (MySQL Community Server - GPL) 外键定义外键（foreign key）...
分块算法
分块算法 简述 其实，分块是一种思想，而不是一种数据结构，整体维护，局部暴力 分块算法实质上是一种是通过分成多块后在每块上打标记以实现快速区间修改，区间查询的一种算法。其均摊时间复杂度为$O(\sqrt{n})$，在$n=10^5$时，由于常数小，跟线段树可能差不多。 分块算法相较于各种树形数据结构，具有简便易写，方便调试等多种优点。在同等数据规模下，如 1e5 ，其时间效率并不会低太多，在考试时反而是一种有力的得分方法。 基本操作及性质为了使得其有着最稳定的时间复杂度，我们经常把一个长度为 n 的序列分为 $\sqrt{n}$个大小为$\sqrt{n}$的块，如果 n 不是完全平方数，则序列最右端会多出一个角块（其实是根据均值不等式，这样划分是时间复杂度最小的） 如下图，就是一种序列的分块： 该长度为 10 的序列被分为了 4 块，前三块的大小为 $\sqrt{10}$的近似值 3 ，最后一个角块大小为 1 而我们要记录的一个值，就是每个序号代表的数，属于哪一块 如上图， 1,2,3就属于第一块， 4,5,6就属于第二块，7,8,9就属于第三块，10...
Java虚拟机笔记-ServiceLoader
ServiceLoader-javaDoc 1234567891011121314151617181920package indi.greenhat.jvm;import java.sql.Driver;import java.sql.DriverManager;import java.util.Iterator;import java.util.ServiceLoader;public class Test { public static void main(String[] args) throws Exception { ServiceLoader<Driver> loader = ServiceLoader.load(Driver.class); Iterator<Driver> iterator = loader.iterator(); while (iterator.hasNext()) { Driver driver =...
Java虚拟机笔记-线程上下文加载器
线程上下文加载器 线程上下文类加载器重要性首先我们看两行输出语句，第一个是输出Thread对象的上下文类加载器，而第二个是输出Thread类的加载器 123456789101112131415161718192021package indi.greenhat.jvm;public class Test { public static void main(String[] args) throws Exception{ /** * currentThread(): * 返回对当前正在执行的线程对象的引用 */ /** * getContextClassLoader(): * 返回此Thread的上下文ClassLoader * 上下文ClassLoader由线程的创建者提供，供加载类和资源时在此线程中运行的代码使用 * 如果未设置，则默认为父线程的ClassLoader上下文 *...