线段树+字典树

78 阅读 0 评论 52 点赞

我是靠谱客的博主害羞短靴，最近开发中收集的这篇文章主要介绍线段树+字典树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

线段树
线段树，是一种二叉搜索树。它将一段区间划分为若干单位区间，每一个节点都储存着一个区间。它功能强大，支持区间求和，区间最大值，区间修改，单点修改等操作。
线段树的思想和分治思想很相像。
线段树的每一个节点都储存着一段区间[L…R]的信息，其中叶子节点L=R。它的大致思想是：将一段大区间平均地划分成2个小区间，每一个小区间都再平均分成2个更小区间……以此类推，直到每一个区间的L等于R（这样这个区间仅包含一个节点的信息，无法被划分）。通过对这些区间进行修改、查询，来实现对大区间的修改、查询。
这样一来，每一次修改、查询的时间复杂度都只为O(log2n) O(log_2n)O(log 2 n)。

01字典树
01字典树是一棵二叉树，每条节点的两条边分别表示二进制的某一位值是0还是1，
将某个从根节点出发路径上边的值连起来就可以得到一个二进制串，这个二进制串是从根节点出发且最高位靠与根节点相连
.通过贪心的策略来寻找与x异或结果最大的数，即优先找和 x二进制的未处理的最高位值不同的边对应的点，这样保证结果最大

http://poj.org/problem?id=3468

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<list>
using namespace std;
const int INF = 0x3f3f3f3f;
#define LL long long int 
long long  gcd(long long  a, long long  b) { return a == 0 ? b : gcd(b % a, a); }
 
 
 
const int N = 100005;
LL a[N];					
LL  lazy[N << 2];			
int n, q;
struct Tree
{
	int l, r;
	LL sum;
	int mid()
	{
		return (l + r) >> 1;
	}
}tree[N<<2];		
 
void PushUp(int rt)
{
	tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
}
 
void PushDown(int rt,int m)
{
	if (lazy[rt])
	{
		lazy[rt << 1] += lazy[rt];
		lazy[rt << 1 | 1] += lazy[rt];
		tree[rt << 1].sum += lazy[rt] * (m - (m >> 1));
		tree[rt << 1 | 1].sum += lazy[rt] * (m >> 1);
		lazy[rt] = 0;
	}
}
 
void build(int l, int r, int rt)
{
	tree[rt].l = l;
	tree[rt].r = r;
	lazy[rt] = 0;
	if (l == r)
	{
		tree[rt].sum = a[l];
		return;
	}
	int m = tree[rt].mid();
	build(l, m, (rt << 1));
	build(m + 1, r, (rt << 1 | 1));
	PushUp(rt);
}
 
void update(LL c, int l, int r, int rt)
{
	if (tree[rt].l == l&&tree[rt].r==r)
	{ 
		lazy[rt] += c;
		tree[rt].sum += c*(r - l + 1);
		return;
	}
	if (tree[rt].l == tree[rt].r)return;
	int m = tree[rt].mid();
	PushDown(rt, tree[rt].r - tree[rt].l + 1);
	if (r <= m)update(c, l, r, rt << 1);
	else if (l > m)update(c, l, r, rt << 1 | 1);
	else 
	{
		update(c, l, m, rt << 1);
		update(c, m + 1, r, rt << 1 | 1);
	}
	PushUp(rt);
}
 
LL Query(int l, int r, int rt)
{
	if (l == tree[rt].l&&r == tree[rt].r)
	{
		return tree[rt].sum;
	}
	int m = tree[rt].mid();
	PushDown(rt, tree[rt].r - tree[rt].l + 1);
	LL res = 0;
	if (r <= m)res += Query(l, r, rt << 1);
	else if (l > m)res += Query(l, r, rt << 1 | 1);
	else
	{
		res += Query(l, m, rt << 1);
		res += Query(m + 1, r, rt << 1 | 1);
	}
	return res;
}
 
int main()
{
	while (scanf("%d%d", &n, &q) != EOF)
	{
		for (int i = 1; i <= n; i++)
			scanf("%lld", &a[i]);
		build(1, n, 1);
		char t;
		int a, b;
		LL c;
		while (q--)
		{
			getchar();
			scanf("%c", &t);
			if (t == 'Q')
			{
				scanf("%d %d", &a, &b);
				printf("%lldn", Query(a, b, 1));
			}
			else if (t == 'C')
			{
				scanf("%d %d %lld", &a, &b, &c);
				update(c, a, b, 1);
			}
		}
	}
	getchar();
	getchar();
}

https://cn.vjudge.net/problem/HDU-4825

#include <bits/stdc++.h>
using namespace std;
#define maxn 100000
#define ll long long
int tol;
ll val[32*maxn];
int ch[32*maxn][2];
void init(){
  tol=1;
  ch[0][0]=ch[0][1]=0;
}
void insert(ll x){
  int u=0;
  for(int i=32;i>=0;i--){
    int v=(x>>i)&1;
    if(!ch[u][v]){
      ch[tol][0]=ch[tol][1]=0;
      val[tol]=0;
      ch[u][v]=tol++;
    }
    u=ch[u][v];
  }
  val[u]=x;
}
ll query(ll x){
  int u=0;
  for(int i=32;i>=0;i--){
    int v=(x>>i)&1;
    if(ch[u][v^1]) u=ch[u][v^1];
    else u=ch[u][v];
  }
  return val[u];
}
int main(){
  int T,n,m;
  ll a;
  scanf("%d",&T);
  for(int s=1;s<=T;s++){
    init();
    scanf("%d %d", &n, &m);
    for(int i=0;i<n;i++){
      scanf("%lld", &a);
      insert(a);
    }
    printf("Case #%d:n", s);
    for(int i=0;i<m;i++){
      scanf("%lld", &a);
      printf("%dn", query(a));
    }
  }
}