Algorithm(2)

算法

 2024/09/24 

树状数组

是线段树的子集。也就是说他能干的线段树都能干，它干不了的线段树也能干。只是这个结构在空间上优化很大，不需要额外空间就能实现。同时编程也靠lowbit大大简化

解决什么问题？

单点修改，区间查询混合，将平均复杂度降到$O(logn)$

考虑两个极端，修改时间度

内容

把n个元素的数组重新组织一下（树操作，不要0下标），奇数还是存自己，偶数存某种前缀和。这个“某种”采用一个独特的方式计算：lowbit——即当前下标二进制表示，从右向左第一个1以及其右边所有0所代表的数。

而lowbit的代码实现也是它速度快的一个保障：

1
2
3

#define lowbit(x) ((x)&(-x))
// start idx:
int start_idx = i - lowbit(i) + 1;

原本数组下标i的元素被放在了树状数组的哪里？我们采用如下计算方法：

1	a[i] in c[i],c[i=i+(lowbit(i))],c[i=i+(lowbit(i))]...

操作

建立

更新

这个操作的具体实现取决于功能。查区间和就+，乘积就乘。

void update(int i, int data){
    while(i<=n){
        c[i] += data;// modify
        i+=lowbit(i);
    }
}

查询

反过来，和前缀和数组的下标转化靠的是减去lowbit(i)查询从1到i的和：

int sum(int i){
    int s=0;
    while(i>0){
        s+=c[i];
        i-=lowbit[i];
    }
    return s;
}

线段树

内容

将正常的数组（连续的元素）换成树的结构进行存储，采用二分形式，原本的每个元素都变成一个叶子结点，然后添加结点让它变成一颗树，其中每个节点保存了它管辖的区间的左右端（相等是叶子）和额外的信息，比如区间和等等，每个节点可操作性很强，因此同时可以允许惰性修改。

对于一个长度为N的输入，线段数需要4N的空间（数组开4倍长）

建立

void build(int root_idx,int left,int right) {
    //printf("build(%d,%d,%d)\n",root_idx,left,right);
	tree[root_idx].left=left;
	tree[root_idx].right=right;
	if(left==right){
		tree[root_idx].min=input[left];//叶子结点，对应具体的元素 
        return;
	}
	int mid=(left+right)>>1;
	build(root_idx*2,left,mid);
	build(root_idx*2+1,mid+1,right);
	tree[root_idx].min=min(tree[root_idx*2].min,tree[root_idx*2+1].min);
	return;
}

查询

修改

并查集

Next Post

Algorithm(1)
Previous Post

Windows函数隐藏——逆向工程实验2022WP

CATALOG

1.
2. 树状数组
3. 线段树
4. 并查集