7-26 学习资料

常规
1

7-26 树状数组&字典树

小组：林育辰，郑荣，许文博，刘天顺

树状数组

原理：

(随便了,反正我也看不懂)

lowbit

  • lowbit(6)=2,lowbit(32)=32,lowbit(31)=1

  • (6)_{10}=(0110)_2,(32)_{10}=(0100000)_2,(31)_{10}=(0011111)_2

计算: lowbit(x)=((x)\&(-x))

对于 a_n 建立的树状数组 b_n ，其中第 i 项满足: b_i=\sum_{j=i-lowbit(i)+1}^i a_j (可能打错了)

前缀和查询:

代码:

while(x){
	ans+=b[x];
    x-=lowbit(x);
}

单点修改:

代码:

while(x<=n){ // n长度,k修改的数
    b[x]+=k;
    x+=lowbit(x);
}

区间查询 O(n) :

( qs,这都不会 )

sum_{i,j}=sum_{j}-sum_{i}

建树 build\ O(n) :

for(int i=1;i<=n;i++){
    s[i]=s[i-1]+a[i],b[i]=s[i]-s[i-lowbit[i]];
}

单点修改 Plus\to 区间修改:

方法: 差分

(不想记录，还不如打线段树)

树状数组优点:

  • 常数小，代码短

应用：

例1: 求逆序对:

  • 方法 1: 权值树状数组 (懒得记录)

  • 方法 2: 归并排序

    (Copy的) Code:

    #include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn=5e5+5;
//下面就是 归并排序求逆序对 的过程==
int a[maxn],r[maxn],n;
ll ans=0;//ans作为全局变量，记录逆序对的数量； 
void msort(int s,int t){
	if(s==t) return ;
	int mid=(s+t)>>1;
	msort(s,mid),msort(mid+1,t);//→→→→→→→递归的体现
	int i=s,j=mid+1,k=s;
	while(i<=mid&&j<=t)
		if(a[i]<=a[j]) r[k++]=a[i++];//先赋值再+1 
		else r[k++]=a[j++],ans+=(ll)mid-i+1;//可以理解为上面的数学归纳吧qaq
	while(i<=mid) r[k]=a[i],k++,i++;
	while(j<=t) r[k]=a[j],k++,j++;
	for(int i=s;i<=t;i++) a[i]=r[i];//复制回a数组中 
}
inline int read(){//快读
	char ch=getchar();
	int x=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x*f;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) a[i]=read();
	msort(1,n);//从1到n将a数组排序;
	printf("%lld\n",ans);
	return 0;
}

例2:洛谷 P1966 [NOIP2013 提高组] 火柴排队

  • 方法 1: 归并排序

    (肯定是拷的) AC\ Code:

    #include<cstdio>
#include<algorithm>
using namespace std;
typedef struct n{
    int num,ord;
}node;
node first_team[100010],second_team[100010];
int a[100010],b[100010],ans;
int compare(node x,node y){
    return x.num<y.num;
}
void Merge(int l,int r){
    if(l>=r) return ;
    int mid=(l+r)/2;
    Merge(l,mid);
    Merge(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            b[k++]=a[j++];
            ans+=mid-i+1;
            ans%=99999997;
        }
        else b[k++]=a[i++];
    }
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(int i=l;i<=r;i++)
        a[i]=b[i];
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&first_team[i].num);
        first_team[i].ord=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&second_team[i].num);
        second_team[i].ord=i;
    }
    sort(first_team+1,first_team+n+1,compare);
    sort(second_team+1,second_team+n+1,compare);
    for(int i=1;i<=n;i++)
        a[first_team[i].ord]=second_team[i].ord;
    Merge(1,n);
    printf("%d",ans);
    return 0;
}

  • 方法 2 : 树状数组

例3 :洛谷 P1972 [SDOI2009] HH的项链

Trie树

长相:

540×700 87.3 KB

（其实是 26 叉树）

建树:

struct trie{
    int tree[100000][26],cnt;
	bool isword[100000];
    
    void insert(string s,int len){
        int pos=0;
        for(int i=0;i<len;i++){
            int id=s[i]-'a';
            if(!tree[pos][id]) tree[pos][id]=++cnt;
            pos=tree[pos][id];
        }
        isword[pos]=1;
    }
    
    bool find(string s,int len){
        int pos=0;
        for(int i=0;i<len;i++){
			int id=s[i]-'a';
            if(!tree[pos][id]) return 0;
            pos=tree[pos][id];
        }
        return isword[pos];
    }
};
trie T;
int main(){
    string a;
    cin>>a;
    T.insert(a,a.size());
    cout<<T.find(a,a.size())<<"\n";
}

例题:

例 1 洛谷 P2922 [USACO08DEC] Secret Message G

Trie树 Plus \to 0/1 Trie

img
img738×500 11.1 KB

用途: 解决位运算相关问题

例题

例 1 ：

已知 n 个数, 每次都给出 k , 求得 k 与这些数中的某个数的异或值最大为多少.

例 2: 洛谷 P4551 最长异或路径

再薅一篇代码吧

AC \ Code:

#include<bits/stdc++.h>
using namespace std;
struct qwq{
    int v;
    int w;
    int nxt;
}edge[2000001];
int head[2000001];
int cnt=-1;
void add(int u,int v,int w){
    edge[++cnt].nxt=head[u];
    edge[cnt].v=v;
    edge[cnt].w=w;
    head[u]=cnt;
}
int sum[2000001];
void dfs(int x,int fa){//预处理
    for(int i=head[x];~i;i=edge[i].nxt){
        int v=edge[i].v;
        int w=edge[i].w;
        if(v!=fa){
            sum[v]=sum[x]^w;
            dfs(v,x);
        }
    }
}
struct trie{
    int ch[2];
}t[2000001];
int tot;
void build(int val,int x){
    for(int i=(1<<30);i;i>>=1){
        bool c=val&i;//取出二进制下这个数的当前位置
        if(!t[x].ch[c]){
            t[x].ch[c]=++tot;
        }
        x=t[x].ch[c];
    }
}
int query(int val,int x){
    int ans=0;
    for(int i=(1<<30);i;i>>=1){
        bool c=val&i;
        if(t[x].ch[!c]){//如果这一位可以进行异或就沿着这一条往下走
            ans+=i;
            x=t[x].ch[!c];
        }
        else x=t[x].ch[c];//否则就沿着另一条路往下走
    }
    return ans;
}
int main(){
    memset(head,-1,sizeof(head));
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,-1);//预处理出每一个节点到根的异或和
    for(int i=1;i<=n;++i)build(sum[i],0);//建立trie数
    int ans=0;
    for(int i=1;i<=n;++i){
        ans=max(ans,query(sum[i],0));//查询，取最大值
    }
    printf("%d\n",ans);
}

例 3: 洛谷 P5149 会议座位

类似于 P1966 火柴排队

  • 方法 1: 归并排序

    用 map<string,int> 将 string 映射成 int

    让我再薅一篇

    AC \ Code:

    #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
string s;
int n,a[N],b[N];
long long ans;//记得开longlong
map<string,int>m;//map在这里
void merge_sort(int left,int right){//归并排序
	if(left>=right) return;
	int mid = (right-left)/2+left;
	merge_sort(left,mid);
	merge_sort(mid+1,right);
	int i=left,j=mid+1,k=left;
	while(i<=mid && j<=right){
		if(a[i]<a[j]) b[k++]=a[i++];
		else b[k++] = a[j++],ans+=mid-i+1;//增加逆序对
	}
	while(i<=mid) b[k++] = a[i++];
	while(j<=right) b[k++] = a[j++];
	for(int i=left;i<=right;i++) a[i]=b[i];
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//加速cincout
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		m[s]=i;//当前编号
	}
	for(int i=1;i<=n;i++){
		cin>>s;
		a[m[s]]=i;
	}
	merge_sort(1,n);
	cout<<ans;
	return 0;
}
2 个赞