GreenHatHGのBlog

主席树又名可持久化线段树 简介传统意义上的主席树就是可持久化线段树，什么叫可持久化呢？就是这棵树啊，可以记录每一次修改的内容，换句话说，就是可以访问这棵树的历史记录。 常见应用 区间/树上路径第 K 大 区间不同数的个数 很多问题如果用线段树处理的话需要采用离线思想，若用主席树则可直接在线处理。故很多时候离线线段树求解可以转化为在线主席树求解。 注意，主席树本质就是线段树，变化就在其实现可持久化，后一刻可以参考前一刻的状态，二者共同部分很多。一颗线段树的节点维护的是当前节点对应区间的信息，倘若每次区间都不一样，就会给处理带来一些困难。有时可以直接细分区间然后合并，此种情况线段树可以直接搞定；但有时无法通过直接划分区间来求解，如频繁询问区间第k小元素，当然，此问题有比较特殊的数据结构-划分树。其实还有一个叫做归并树，是根据归并排序实现的，每个节点保存的是该区间归并排序后的序列，因此，时间、空间复杂度都及其高， 所以一般不推荐去用。当然，主席树也是可以解决的。 结构由若干棵线段树组成（若是权值线段树通常需先对数据离散化），按照输入顺序，每插入一个数保存一份当前版本的线段树。也就是说，对 ...

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 号课程的课程的学生，并显示他们的姓名。 我们先不管EXISTS关键字在其中起了什 ...

常量池（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, cnt_3=1$，然后我们把qr ...

.class文件 Java从刚开始的时候就有两套 规范，一个是Java语言规范，另外一个是Java虚拟机规范，Java语言规范只是规定了Java语言相关的约束以及规则，而虚拟机规范则才是真正从跨平台的角度去设计的 Java语言的平台无关性在虚拟机出现之前，程序要想正确运行在计算机上，首先要将代码编译成二进制本地机器码，而这个过程是和电脑的操作系统OS、CPU指令集强相关的，所以可能代码只能在某种特定的平台下运行，而换一个平台或操作系统就无法正确运行了。随着虚拟机的出现，直接将程序编译成机器码，已经不再是唯一的选择了。越来越多的程序语言选择了与操作系统和机器指令集无关的、平台中立的格式作为程序编译后的存储格式。Java就是这样一种语言。“一次编写，到处运行”于是成立Java的宣传口号。 正是虚拟机和字节码(ByteCode)构成了平台无关性的基石，从而实现“一次编写，到处运行” Java虚拟机将.java文件编译成字节码,而.class字节码文件经过JVM转化为当前平台下的机器码后再进行程序执行。这样，程序猿就无需重复编写代码来适应不同平台了，而是一套代码处处运行，至于字节码怎样转化 ...

通过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 url = ...

外键与级联更新删除 之前没用过外键与级联更新，所以总结一下，用的数据库版本： mysql Ver 8.0.15 for linux-glibc2.12 on x86_64 (MySQL Community Server - GPL) 外键定义外键（foreign key） 是用于建立和加强两个表数据之间的链接的一列或多列。外键约束主要用来维护两个表之间数据的一致性。简言之，表的外键就是另一表的主键，外键将两表联系起来。一般情况下，要删除一张表中的主键必须首先要确保其它表中的没有相同外键（即该表中的主键没有一个外键和它相关联）。 MySQL有两种常用的引擎类型：MyISAM和InnoDB。目前只有InnoDB引擎类型支持外键约束。 外键的好处：可以使得两张表关联，保证数据的一致性和实现一些级联操作； 外键术语 外键约束 外键字段：某个字段添加外键约束之后，该字段称为外键字段 外键值：外键字段中的每一个数据都是外键值 具体实例什么？看完定义还不知道是什么？那就试试看下面咯 当我们用主键唯一标识记录时，我们就可以在students表中确定任意一个学生的记录： id name ...

分块算法 简述 其实，分块是一种思想，而不是一种数据结构，整体维护，局部暴力 分块算法实质上是一种是通过分成多块后在每块上打标记以实现快速区间修改，区间查询的一种算法。其均摊时间复杂度为$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 就属于第四块 可以 ...

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 = iterator.next ...

线程上下文加载器 线程上下文类加载器重要性首先我们看两行输出语句，第一个是输出Thread对象的上下文类加载器，而第二个是输出Thread类的加载器 123456789101112131415161718192021package indi.greenhat.jvm;public class Test { public static void main(String[] args) throws Exception{ /** * currentThread(): * 返回对当前正在执行的线程对象的引用 */ /** * getContextClassLoader(): * 返回此Thread的上下文ClassLoader * 上下文ClassLoader由线程的创建者提供，供加载类和资源时在此线程中运行的代码使用 * 如果未设置，则默认为父线程的ClassLoader上下文 * 原始线程的上下文Clas ...