线段树(区间树)

什么是线段树线段树也称区间树,更多的用于查询数据区间的值。线段树和二分搜索树相似也是二叉树,但具体的现实是不一样的。线段树对于需要频繁动态更新和查询的数据是比普通算法是更有利。(当然lazy我暂时留个坑有空再填)时间复杂度查询修改普通算法O(1)O(n)线段树O(logn)O(logn)下方图以数值区间求和为例,每个节点的数值的和都平坦到子节点上。所以查询的时候只需要访问到区间节点就好了,而不需要每个值都访问。例如:数组A[0,1,2,3,4,5,6,7] 查询0到3的区间值,只需要访问到根节点的右子节点就可以拿到区间值。当然线段树不只是可以拿来做区间求和也可以拿来比较最大值或最小值等操作。线段树的构建样例图:用数组实现线段树用数组实现线段树需要用把它当作满二叉树存储。对于满二叉树h层一共有2^h-1个节点。最后一层(h-1) 有2^(h-1)个节点。如果n=2^k 只需要2n的空间,但是最坏的情况为n=2^k+1 所以需要开4n的空间 (右边高度比左边高度多1层)例子:计算区间值的和构建算法大概为从中间分开 为左右子节点。(同时计算或比较等操作)左子节点:父节点下标*2+1右子...

Java多线程基础

进程与线程进程:是计算机中的程序关于某数据集合上的一次运行活动,是系统进行资源分配和调度的基本单位,是操作系统结构的基础。线程:是操作系统能够进行运算调度的最小单位。它被包含在进程之中,是进程中的实际运作单位。每个程序都是一个进程,一个进程里面可以包含多个线程。(比如你在听歌的时候是一个线程,下载音乐又是另一个线程,它们不会互相干扰),线程之间可以共享进程的资源。Java多线程Java虚拟机允许应用程序同时执行多个执行线程。1、继承ThreadThread常用的方法Modifier and TypeMethodDescriptionvoidstart()导致此线程开始执行; Java虚拟机调用此线程的run方法。static voidsleep(long millis)使当前正在执行的线程以指定的毫秒数暂停(暂时停止执行),具体取决于系统定时器和调度程序的精度和准确性。 会占用线程的睡眠voidjoin()等待这个线程死亡。static voidyield()对调度程序的一个暗示,即当前线程愿意产生当前使用的处理器。voidrun()如果这个线程使用单独的Runnable运行对...

MySQL 存储过程

存储过程(Stored Procedure)是一种在数据库中存储复杂程序,以便外部程序调用的一种数据库对象。存储过程是为了完成特定功能的SQL语句集,经编译创建并保存在数据库中,用户可通过指定存储过程的名字并给定参数(需要时)来调用执行。存储过程思想上很简单,就是数据库 SQL 语言层面的代码封装与重用。优点存储过程可封装,并隐藏复杂的商业逻辑。存储过程可以回传值,并可以接受参数。存储过程无法使用 SELECT 指令来运行,因为它是子程序,与查看表,数据表或用户定义函数不同。存储过程可以用在数据检验,强制实行商业逻辑等。缺点存储过程,往往定制化于特定的数据库上,因为支持的编程语言不同。当切换到其他厂商的数据库系统时,需要重写原有的存储过程。存储过程的性能调校与撰写,受限于各种数据库系统。staffs表结构idnameage1李虎132张三143李四13delimiter $$  #将语句的结束符号从分号;临时改为两个$$(可以是自定义) CREATE PROCEDURE delete_by_id(IN id INTEGER) ##定义存储过程和传参 BEGIN #存储过程开始 ...

P1583 魔法照片

题目描述一共有n(n≤20000)个人(以1--n编号)向佳佳要照片,而佳佳只能把照片给其中的k个人。佳佳按照与他们的关系好坏的程度给每个人赋予了一个初始权值W[i]。然后将初始权值从大到小进行排序,每人就有了一个序号D[i](取值同样是1--n)。按照这个序号对10取模的值将这些人分为10类。也就是说定义每个人的类别序号C[i]的值为(D[i]-1) mod 10 +1,显然类别序号的取值为1--10。第i类的人将会额外得到E[i]的权值。你需要做的就是求出加上额外权值以后,最终的权值最大的k个人,并输出他们的编号。在排序中,如果两人的W[i]相同,编号小的优先。输入格式第一行输入用空格隔开的两个整数,分别是n和k。第二行给出了10个正整数,分别是E[1]到E[10]。第三行给出了n个正整数,第i个数表示编号为i的人的权值W[i]。输出格式只需输出一行用空格隔开的k个整数,分别表示最终的W[i]从高到低的人的编号。输入输出样例输入 #110 10 1 2 3 4 5 6 7 8 9 10 2 4 6 8 10 12 14 16 18 20输出 #110 9 8 7 6 5 4...

AVL树主要代码清单

/*返回树的高度*/ int GetHeight(SubTree T) { if (!T) return 0; else return T->height; } int Max(int a, int b) { return (a > b) ? a : b; } /*左子树的左边就要 往右转*/ SubTree LLRotate(SubTree T) { SubTree Tmp; Tmp = T; T = T->left; Tmp->left = T->right; T->right = Tmp; /*维护高度*/ Tmp->height = Max(GetHeight(Tmp->left), GetHeight(Tmp->right)) + 1; T->height = Max(GetHeight(T->left), GetHeight(T->right)) + 1; ret...