《树状数组及其应用双语版讲述》由会员分享，可在线阅读，更多相关《树状数组及其应用双语版讲述（87页珍藏版）》请在金锄头文库上搜索。
1、树状数组及其应用 Binary Indexed Tree 引例 【题目描述】 输入一个数列A1,A2.An(10) t+=ck; k- =lowbitk; return t; 在实际应用中，通常不需要保存原数组a， 只保存数组c即可。因此，树状数组几乎不 需要附加空间。 通过上面的学习可以看出：树状数组所能 支持的操作是修改点值、查询区间和。 与线段树和其他数据结构相比，树状数组 代码简单，常数小，在其能解决范围内或 经过转化使用树状数组，可以极大的降低 编程复杂度，使代码清晰，简洁 优秀的数据结构！ 例题、Stars(ural 1028) 题目大意 平面中有N个点，对于 每个点(x,y)，要
2、求输 出在其左下方（包括正 左正下）点的个数。 N0 do begin t:=t+cx,z; z:=z-lowbit(z); end; x:=x-lowbit(x); end; getsum:=t; End; 对于询问(x1,y1)-(x2,y2)， ans=getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1- 1,y2) +getsum(x1-1,x2-1); 树状数组下标必须从1开始 Superbrother 神牛 到此，我们已经学习完树状数组的基本内 容。 树状数组的应用非常广泛，变形极多，灵 活性强，很多题目经过一系列转化后可以 使用树状数组解决。 下面，我
3、将通过其他几个例题介绍如何通 过有效的转化使用树状数组解题。 3、Cows(pku 2481) 题目大意 有n头牛，每头牛喜欢吃si,ei这个区间的 草。如果对于i、j两头牛，siaj。 首先对a数组离散化 按顺序扫描，只需找到有多少比ai大的数 已经出现过。这可以用树状数组维护。 初始时，数组全为0。每次扫描到ai，用树 状数组求出ai+1max中出现过多少个数 ，然后将ai插入树状数组。 例如n=5,输入100 6 7 2 3 首先离散化，输入变为5 3 4 1 2 顺序扫描 i12345 100000 例如n=5,输入100 6 7 2 3 首先离散化，输入变为5 3 4 1 2 顺序扫
4、描 i12345 200001 例如n=5,输入100 6 7 2 3 首先离散化，输入变为5 3 4 1 2 顺序扫描 i12345 300101 例如n=5,输入100 6 7 2 3 首先离散化，输入变为5 3 4 1 2 顺序扫描 i12345 400111 例如n=5,输入100 6 7 2 3 首先离散化，输入变为5 3 4 1 2 顺序扫描 i12345 510111 小结 以上几道例题比较简单，属于树状数组的 基础用法，主要起到数据结构的作用，用 来对数据进行快速的存储和处理。 树状数组与其他数据结构相比，最大的特 点就是代码简单，常数小，从而得到广泛 的应用。 树状数组的基本
5、操作就是两个，修改某个 元素的值，求区间累加和。 括号 括号表示法是运用树状数组解题的重要方 法之一。 应用括号表示，可以将一部分修改区间、 查询点值的题目转化为修改点值、查询区 间，从而可以使用树状数组。 5、Superbrother种树 实验中学东校坐落在济南市郭店镇。为了 迎全运，树新风，需要在一条长为n的道路 上种若干种树。道路表示为0,n，共n+1个 点。由于经费紧张，教导处将这个重任交 给了信息组头号神牛Superbrother，希望他 合理分配树木，使道路更加漂亮。 Superbrother经过研究，制定了一套详细的 计划。计划可以描述为若干个操作，每个 操作在l,r中所有点种一
6、棵颜色特殊的树。 教导处随时都会检查，方式为给定一个点 ，要求他回答这个点一共种过多少种不同 的树。 输入第一行为n,m 以下m行，可能是一次种 树，也可能是一次询问。 此题与前面几题不同，要求修改一段区间 的值，询问一个点的值。 使用线段树可以轻松处理。 有没有更简单、快速的方法？ 利用括号，转化为树状数组 要将修改区间操作转化为修改点的操作， 只有在区间端点做文章。 每次修改区间，便在区间两端加括号。这 样，每次询问时只需要输出从0这个点中 左括号数-右括号数。 具体的，对于每个修改操作l,r，将树状数 组中cl+1,cr+1-1。对于询问操作t，输出 getsum(t)。 时间复杂度O(
7、mlgn) 6、Matrix(pku 2155) 题目大意 给定一个n*n的01矩阵，初始全部为0。要 求维护两个操作： 1、C x1 y1 x2 y2 ，子矩阵(x1,y1)(x2,y2) 中数 值全部取反 2、Q x y ，询问点(x,y)的值 样例输入 样例输出 2 10 1 C 2 1 2 2 0 Q 2 2 0 C 2 1 2 1 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 此题是区间求反问题，而树状数组所维护 的是区间和问题。 如何转化？ 注意到所求为一个点 的值，而点值只与 求反操作次数有关 首先考虑一维
8、情况 原问题变为：对于一个数列，每次对一段 区间取反，询问一个点的值。 由于一个点的值只与取反次数有关，所以 我们记录每个点的取反次数。 树状数组支持的操作是修改一个点的值， 查询一段区间的和。而此题恰恰相反。 如何改变树状数组的意义？ 括号 每次对一段区间(a,b)取反，可以看成加了 一对括号。 每次询问只需求出从1到k中左括号-右括号, 即为点k修改的次数 数组ci记录1i中左括号-右括号的值。 每次修改(a,b),ca加1，cb+1减1。 这样，每次询问求出ck，判断奇偶即可。 如何推广到二维？ 查询操作不变，对于每次修改操作 (x1,y1)- (x2,y2)，我们仿照一维情形加“括号”
9、。 具体的 cx1,y1+1,cx2+1,y2+1+1 cx1,y2+1-1,cx2+1,y1-1 7、密码机 题目大意 有一个初始为空的序列。维护三种命令： 1、ADD把Number加到数列最后 2、REMOVE在数列中找到等于 的数，删除 3、xor between and 对于数列中所有在 Number1,Number2中的数异或并输出结 果 加入的数不超过20000，询问次数=60000 算法一：直接处理 对于Add操作，直接将Number添加到数组 尾端。O(1) 对于Remove操作，直接查询并删除。O(n) 对于Xor操作，枚举每一个元素。O(n) 时间复杂度O(T*n) 小优化
10、 Xor操作即按位异或. 1 xor 1=0. 1 xor 0=1. 0 xor 0=1. 对于delete操作，我们其实可以将其视为 Add操作。因为a xor a=0. a xor 0=a，所以 delete(Number)将相当于add(Number) 这样Delete操作复杂度降到(1) 算法的瓶颈在于询问操作 由于询问操作可能达到O(n)，所以如果要 降低时间复杂度，就不能枚举全部符合条 件的数然后异或，只能利用某些方法一起 计算。 观察输入，我们发现加入的数不超过20000 ，如何利用这个条件？ 树状数组! 算法二：树状数组 将Add操作和Delete操作看成Add，把树状 数组操
11、作中加法改成xor。可以证明，这种 方法可以得到正确的结果。 对于询问l,r，因为a xor a=0,a xor 0=a， 可以直接输出get(r) xor get(l-1) 每个操作复杂度均为logn，总时间复杂度为 O(Tlogn) 8、Jason911追MM Ssfz神牛颇多，但最会追MM的当属 Jason911。这一天jason911发现n个MM， jason911非常高兴，很想让她们全当自己GF 。但是她发现如果如果找太多GF会让她们很 不满意，于是他决定只找5个MM当GF。 MM们按顺序排成1n，各有一个魅力值。 Jason911决定，他要使找到GF的魅力值严 格递增，这样才能心情
12、愉快。 他想知道一共有多少种选法 例如有7个MM，魅力值分别为2, 1, 3, 4, 5, 7, 6。合法的取法有4种，分别为1, 3, 4, 5, 6, 2, 3, 4, 5, 6, 1, 3, 4, 5, 7和2, 3, 4, 5, 7。 MM最多有50000个 对于一般的LIS，可以使用动态规划，运用 二分可以达到(nlogn)。 本题要求方案数，朴素的DP可以另维护一 个数组gi,j表示表示以i为结尾、长度为j的 上升子序列的种数。 能否仍用二分，同时求出方案数？ 考虑使用树状数组记录次数和长度 此题要求LIS长度为5，即可分为5个阶段。 分别为15，各开一个树状数组，记录方 案数。
13、具体的，扫描到每个MM时，首先将其加入 到第一个树状数组，然后j从1循环到4，判 断能够找到多少魅力值小于她的MM，并加 入到下一个树状数组。 长度 1234567 1+1 2 3 4 5 2, 1, 3, 4, 5, 7, 62, 1, 3, 4, 5, 7, 6 i i j j 长度 1234567 1+11 2 3 4 5 2, 1, 3, 4, 5, 7, 62, 1, 3, 4, 5, 7, 6 i i j j 长度 1234567 111+1 2+2 3 4 5 2, 1, 3, 4, 5, 7, 62, 1, 3, 4, 5, 7, 6 i i j j 长度 1234567 11
14、11+1 22+3 3 4 5 2, 1, 3, 4, 5, 7, 62, 1, 3, 4, 5, 7, 6 i i j j 长度 1234567 11111 223 3+2 4 5 2, 1, 3, 4, 5, 7, 62, 1, 3, 4, 5, 7, 6 i i j j 长度 1234567 11111+1 223+4 32 4 5 2, 1, 3, 4, 5, 7, 62, 1, 3, 4, 5, 7, 6 i i j j 长度 1234567 111111 2234 32+5 4 5 2, 1, 3, 4, 5, 7, 62, 1, 3, 4, 5, 7, 6 i i j j 长度
15、1234567 111111 2234 325 4+2 5 2, 1, 3, 4, 5, 7, 62, 1, 3, 4, 5, 7, 6 i i j j 长度 1234567 111111+1 2234+5 325 42 5 2, 1, 3, 4, 5, 7, 62, 1, 3, 4, 5, 7, 6 i i j j 长度 1234567 1111111 22345 325+9 42 5 2, 1, 3, 4, 5, 7, 62, 1, 3, 4, 5, 7, 6 i i j j 长度 1234567 1111111 22345 3259 42+7 5 2, 1, 3, 4, 5, 7, 62, 1, 3, 4, 5, 7, 6 i i j j 长度 1234567 1111111 22345 3259 427 5+2 2,
