Accelerator‘s Blog

经过近一周的学习与刷题，我在这段时间还是学到了一些东西的，这里做一下总结和计划。

关于数据结构：

线段树：包含了二分的思想在其中，是用来优化时间复杂度的利器；

树状数组：就是运用前缀和的思想来维护一棵树，利用这棵树中的性质达到快速查询的目的。

自己写的模板：

树状数组（维护+询问）：

#include<cstdio>
#include<cstdlib>
using  namespace std;
#define maxn 200000+5
int a[maxn],n;

inline int lowbit(int x){
	return x&(-x);
}
void updata(int x,int d){
	while(x<=n){
		a[x] += d;
		x += lowbit(x);
	}
}
int sum(int x){		
	int tot = 0;
	while(x > 0){
		tot += a[x];
		x -=lowbit(x);
	}
	return tot;
}

Hash（维护+询问）：

#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
#define maxn 100007
struct node{
	int value;
	node *link;
}hash[maxn];
void updata(int x)
{
	int tmp = x % maxn;
	node *cur;
	cur = (node*)malloc(sizeof(node));
	cur->value = x;
	cur->link  = hash[tmp].link;
	hash[tmp].link = cur;
}
bool query(int x)
{
	int tmp = x % maxn;
	node *cur;
	cur = hash[tmp].link;
	while(cur != NULL)
	{
		if(cur->value == x)return 1;
		cur = cur->link;
	}
	return 0;
}