ACM中的数据结构.ppt

算法实现 算法实现 样例输入 5 6 1 2 3 4 5 QUERY 1 3 ADD 1 2 QUERY 1 3 ADD 2 3 QUERY 1 2 QUERY 1 5 样例输出 6 8 8 20 树状数组推广 二维树状数组 求sum{a[1..m][1..n]} 维护和查询复杂度均为O(logm*logn) 用于动态求子阵和,数组内容保存在sum.a[][]中 还可以进一步推广到三维树状数组 练习 链接：/JudgeOnline/problem.php?pid=1089 描述 提供一个N*N的矩阵，其中每一个格子中的数不是1就是0，初始时每一个格子的值为0，我们可以修改这个矩阵中的数字，每次给出矩阵的左上角坐标(x1,y1)，以及右下角的坐标(x2, y2)，并且将矩阵中的数字全部取反（原来是1现在变成0，原来是0现在变成1）,还可以每次查询第x行第y列的格子中的数字是什么。 T 100,N 1000 , Q 50000. 输入 Line1：给出一个T，表示组数 Line2:给出两个数N，Q.矩阵大小，询问次数 Line：3...3+Q: 输入C，则后又四个数(x1,y1),(x2,y2) 输入Q，则后两个数(x,y) 输出 每次询问输出查询结果。 样例输入 1 2 10 C 2 1 2 2 Q 2 2 C 2 1 2 1 Q 1 1 C 1 1 2 1 C 1 2 1 2 C 1 1 2 2 Q 1 1 C 1 1 2 1 Q 2 1 样例输出 1 0 0 1 线段树 线段树是一种二叉有哪些信誉好的足球投注网站树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。 参考论文： 数据结构的选择与算法效率 ——从IOI98试题PICTURE谈起 线段树解决的基础问题 1.数组数组能解决的所有问题（插点问线、插线问点、逆序数、第k大等） 2.插线问线（lazy标记） 3.各种区间更改、查询问题 练习 链接：/JudgeOnline/problem.php?pid=1068 描述 已知N（1=N=10005）个随机整数，对这些数可能有以下几种操作或询问： 1. A a b c 表示给区间a到b内每个数都加上c； 2. S a b 表示输出区间a到b内的和； 3. Q a b 表示输出区间a到b内的奇数的个数； 接下来有M（1=M=10000，M为询问次数）次操作，对于操作2和3，输出结果。 样例输入 5 5 1 2 3 4 5 Q 1 4 S 1 5 A 1 4 1 S 1 5 Q 2 5 样例输出 2 15 19 3 Hash—散列 Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。 数学表述为：h = H(M) ，其中H( )--单向散列函数，M--任意长度明文，h--固定长度散列值 Hash—散列 当两个或两个以上的关键字散列到同一个值的时候，发生冲突。 解决方法：开散列和闭散列 Hash冲突取决于 Hash函数的选择 散列空间的大小 开闭散列 输入数据 字符串散列ELFHash函数 //prime:3001,5003,10007,20011,50021,100003,150001,200003,500009,704447,901963,1009237, 1199993, 1500007,2000003,5000011 int ELFhash(char *key) { unsigned int g,h=0; while (*key){ h=(h4)+(*key++); g=h 0xf0000000L; if (g) h^=g24; h=~g; } return h%Size;//Size要用大质数 } 字符串散列SuperFastHash(1) #define get16bits(d) ((((unsigned int)(d)[1])8)+(unsigned int)(d)[0]) int Su