IndexTree,AC自动机

IndexTree

特点

1. 支持区间查询
2. 没有线段树那么强，但是非常容易改成一维、二维、三维的结构
3. 只支持单点更新

IndexTree的诞生

假如有一个数组,有个需求就是频繁的查询某些区间的累加和.例如7~12的,569~975的,

面对上面的需求,我们搞一个前缀和help数组,其实已经可以搞定了,例如7~12的就是1~12的减去1~7的,查一下减一下,O(1)可以做到.

但是,这都是建立在我help数组搞完了的基础上的,一旦说,某个位置的数变了呢,我辛苦建立的help,后面的数,全部都得重新算,这个成本是很高的.

所以我们需要一个高效的算法,好像这个上面的场景,说的不是线段树吗?不错,线段树能做,但是,IndexTree也有它的优势!

核心算法

人为规定,1开始,

假设数组下标,1,2,3,4,5,6,7,8,9,10,11,12

累加和,help数组[1,(1,2),3,(1~4),5,(5,6),7,(1~8),9,(9~10),11,(9~12)],

那当我有index位置的值变化的时候,我需要更新哪些地方呢?

给index展开为2进制的,然后,去掉最后的1,最后加个1,这个数~index的,就是需要改的范围.

例如,8位置的变了,0001000,那他去掉最后的1,最后加个1,就是00000000,范围就是1~8.

12位置变了,0001100,那他去掉最后的1,最后加个1,就是0001001,范围就是9~12.完全符合上面的规律.

干啥用?

我如何更新我的这个新的辅助数组结构啊.

假设任意的index位置变了,我还是求累加和,哪个位置受牵连?

例如0000110100,上面说了,他这个index位置就是负责0000110100~000011001的,

我们这么算.给他分段.

首先算arr 0110001~0110100,抹掉一个最右侧的1了

然后算arr 010001~0110000,再抹掉一个最右侧的1.

最后算arr 000001~0100000,发现没有,这三段是挨着的.

所以怎么变受牵连的位置的值?

找受牵连的位置,给他们都+变化的值.

首先index位置,要变,然后,下一个,最末尾的1加起来,例如,6位置,110,最末尾的1,是10,加一起,就是1000,8位置,然后再最末尾1加起来,10000,16,然后再加,100000,32,所以说,只要不超过数组范围,一直加,这些都是受牵连的位置.

复杂度,logN,最多也就那么多个1嘛.

while (index <= N) {
				tree[index] += d;
  //负数就是取反+1,提取最右侧的1,就是自己&取反+1
				index += index & -index;
			}

所以怎么求累加和?

前缀树就是后面的减前面的,IndexTree是前面的1的位置的,一点点剥离出来然后怼上去.

while (index > 0) {
				ret += tree[index];
				index -= index & -index;
			}

AC自动机

解决在一个大字符串中，找到多个候选字符串的问题

AC自动机算法核心

1. 把所有匹配串生成一棵前缀树
2. 前缀树节点增加fail指针
3. fail指针的含义：如果必须以当前字符结尾，当前形成的路径是str，剩下哪一个字符串的前缀和str的后缀，拥有最大的匹配长度。fail指针就指向那个字符串的最后一个字符所对应的节点。（迷不迷？听讲述！）