2

树状数组 - <NULL>

 1 year ago
source link: https://www.cnblogs.com/lightcoder/p/16484211.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

1|0树状数组

1|11. 绪论

树状数组本质上是一个 运用了 分块思想 的 前缀和 数组，使得查询和修改的时间复杂度都是O(logN)O(logN) 级别，但由于是一个前缀和数组，所以对于一些区间能做的事情还是十分有限，鉴于树状数组的实现简单，代码量少，对于问题是否使用树状数组还是线段树的情况需要自行辨别

1|22. 模板




#define lowbit(a) a&(-a)
int Trarr[100005];
void add(int x, int val){
    while(x <= MAX_LIMIT){
        Trarr[x] += val;
        x += lowbit(x);
    }
}
int getsum(int x){
    int ans = 0;
    while(x){
        ans += Trarr[x];
        x -= lowbit(x);
    }
    return ans;
}






1|33. 经典模型



  • 

    PUIQ问题 (单点修改及区间求和) OptAOptA . ai+=Pai+=POptBOptB . ∑i[L,R]ai∑[L,R]iai
    

    考虑点 ii 的值发生变化时会影响到树状数组的哪些部分，然后进行更新就可以了，一般是在点 ii加一个负值去消除原数的影响再加入新数，并更新其前继数组，区间求和就和前缀和一样，直接 getsum(R)−getsum(L−1)getsum(R)−getsum(L−1)
    

    见 Luogu P3374
    

    • 

  • 

    IUPQ问题 (区间修改和单点查询) OptOptai+=P,i∈[L,R]ai+=P,i∈[L,R]Quirya[i]Quirya[i]
    

    考虑结合差分算法，区间修改是差分的算法优势，对于单点求值就是差分的前缀和，此时用树状数组来维护差分的前缀和数组就可以解决，对于区间修改直接Add(L,V)Add(R+1,−V)Add(L,V)Add(R+1,−V) 单点求和就相当于查前缀和数组 不再赘述
    

    见 Luogu P3368
    

    • 

  • 

    求逆序数问题 Counti<j,ai>ajCounti<j,ai>aj 如 1,5,2,4,31,5,2,4,3 中的(5,2)(5,2)是一对逆序对
    

    核心思想是记录 在树状数组中记录值为 [1,ai][1,ai] 的个数，注意不是单纯的将数据的值作为树状数组的下标，将树状数组当一个桶用，树状数组本质是一个前缀和数组，这样是行不通的，此时的Add(ai,1)Add(ai,1) 操作就是记录值在[1,ai][1,ai] 的数又多一个, 计算逆序数时就一边遍历，一边将当前的数计入树状数组，然后询问比自己小的数有多少个 即询问值在[1,ai][1,ai]的数有多少个，此时得到的是 i<j,ai<aji<j,ai<aj 的数，再用当前的 ii 减去这个值就能得到这个位置的逆序数
    

    见 Luogu P1966
    

    统计个数的思想十分常用，有时也将树状数组数组全初始化为1或0，来查找第k个此时的值，结合下面的二分
    

    • 

  • 

    二分思想 就是在查找的过程中进行二分枚举
    

    比如你每次可以往容器中丢入一个编号为 ii 的球，或者询问容器中编号第 KK 大的球的编号，显然对于编号第 KK 的球，前面只能有 K−1K−1 个球比他大， 那就有getsum(N)−getsum(x)<=K−1getsum(N)−getsum(x)<=K−1 ，同时由于前缀和的特殊性，树状数组中可能存在多个该情况的数字，此时取第一个数字，由于前缀和必然满足单调性，所以此时可以使用二分来查找满足这个条件的数字
    

    • 

  • 

    区间排序思想 有时为了维护区间或者比较多个区间内的信息，会固定一端进行排序
    

    如给定 NN 个区间，计算第 ii 个区间有多少个区间大于他，此时可以将给定的区间按右端点从大到小排序，右端点相同的则左端点小的排前面，用树状数组维护左端点的插值，即读入第 ii 个区间时，就进行 Add(Li,1)Add(Li,1)，表示[1,Li][1,Li] 这一段中又插入了一个区间，查询时直接询问这一段有多少个区间就可以，因为我们进行了排序，所以保证右端点是递减的。
    

    还有如给定长度为 NN 的一个序列，有 QQ 个询问对于某段区间内的数字有多少种，此时也可进行区间排序，然后一边遍历一边维护，考虑对于第二次出现的数字，在树状数组中消除他在第一次出现的影响，并在第二次出现的位置更新它，即我们此时在树状数组中维护的信息是 [1,R][1,R]中有多少种数，并且保证了出现的数字不重复计算，且始终将其更新到最右端 。
    

    最后计算答案时只要询问 getsum(quiry[i].R)−getsum(quiry[i].L−1)getsum(quiry[i].R)−getsum(quiry[i].L−1)
    

    见 Luogu P4113
    

    • 

  • 

    多维树状数组 有时一维的树状数组无法维护全部信息，此时选择多维记录状态
    

    如一个 N∗MN∗M 的方格，每个格子初始时有一个整数权值，接下来有两种操作:
    

    改变一个格子里权值或者求一个子矩阵中特定权值出现的个数，此时我们选择开一个三维的树状数组，前两维表示位置，第三维表示数字(类逆序数模型)，维护时就用两个for循环去控制位置，然后再对应数字位置上+val+val 如下面代码
    

    #define lowbit(a) a&(-a)
void Tradd(int x, int y, int val, int color){
    for(int i = x; i <= N; i += lowbit(i)){
        for(int j = y; j <= M; j += lowbit(j)){
            Trarr[i][j][color] += val;
        }
    }
}
int Trqui(int x, int y, int color){
    int ans = 0;
    for(int i = x; i; i -= lowbit(i)){
        for(int j = y; j; j -= lowbit(j)){
            ans += Trarr[i][j][color];
        }
    }
    return ans;
}
    


    • 




询问的时候就类似二维前缀和


Trqui(x2,y2,color)−Trqui(x1−1,y2,color)−Trqui(x2,y1−1,color)+Trqui(x1−1,y1−1,color)Trqui(x2,y2,color)−Trqui(x1−1,y2,color)−Trqui(x2,y1−1,color)+Trqui(x1−1,y1−1,color)


不明白的读者可以尝试画一个图就能明白


这题见Luogu P4054


1|44. 大应用题



这里提供一道比较麻烦的例题  Luogu P3960


大概的一个思路每行单独维护，因为互不影响，最后一列比较特殊也需要单独维护，然后离线问题，将问题按照行从小到大排列，然后预处理每列的真实删除位置，比如对于(1,3)(1,3) 是删除第一行第三列数字，第二次删除时就不再是(1,3)(1,3) 了，考虑其先向左对齐，所以下一个删除的数字就是(1,4)(1,4)，我们的预处理就是要找出这个44


这个预处理运用的是一个逆序数模型和二分模型，对于每一个删除的数字，要通过树状数组去预处理，确认这个数字真实的删除位置，维护这个信息需要将树状数组全部初始化成11，查找需要删除的数字时，就二分查找值等于题目指定删除数字的列数，删除后Add(x,−1)Add(x,−1)


然后将问题按照问的顺序重新恢复，在进行模拟，对于真实位置小于列数的情况直接删除就可以，等于列数的情况就直接在最后一列上动手脚，大于列数的情况就额外开一个Vector数组去存每行每列额外的数字，这个最后一列删除的情况也是运用二分+树状数组去处理实际删除的是第几行 然后就AC了


下面是AC代码





#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iostream>
#include <vector>
#define int long long
#define lowbit(a) a&(-a)
using namespace std;
const int maxn = 1e5+5;
int N, M, Q, Tr1[600005], Tr2[600005], last[600005];
vector<int> Extra[300005];
struct info{
    int x, y, pos;
    bool vis;
};
struct info quiry[300005];
void Tr1add(int x, int val){
    while(x <= 600005){
        Tr1[x] += val;
        x += lowbit(x);
    }
}
int Tr1qui(int x){
    int ans = 0;
    while(x){
        ans += Tr1[x];
        x -= lowbit(x);
    }
    return ans;
}
void Tr2add(int x, int val){
    while(x <= 600005){
        Tr2[x] += val;
        x += lowbit(x);
    }
}
int Tr2qui(int x){
    int ans = 0;
    while(x){
        ans += Tr2[x];
        x -= lowbit(x);
    }
    return ans;
}
bool cmp1(info a, info b){
    if(a.x == b.x) return a.pos < b.pos;
    else return a.x < b.x;
}
bool cmp2(info a, info b){
    return a.pos < b.pos;
}
signed main(){
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    scanf("%lld%lld%lld", &N, &M, &Q);
    for(int i = 1; i <= Q; i++){
        scanf("%lld%lld", &quiry[i].x, &quiry[i].y);
        quiry[i].pos = i;
    }
    for(int i = 1; i <= 600005; i++) Tr1add(i, 1), Tr2add(i, 1);
    for(int i = 1; i <= N; i++){
        last[i] = i*M;
    }
    sort(quiry+1, quiry+1+Q, cmp1);
    int Now = 1;
    for(int i = 1; i <= Q; i++){
        int Len = M;
        while(Now < Q && quiry[i].x == quiry[Now+1].x) Now++;
        vector<int> mid;
        for(int j = i; j <= Now; j++){
            if(quiry[j].y == M){ 
                quiry[j].vis = true;
                continue;
            }
            int L = 1, R = Len;
            while(R > L){
                int MID = (R+L) / 2;
                if(Tr1qui(MID) >= quiry[j].y) R = MID;
                else L = MID+1;
            }
            mid.push_back(L); Tr1add(L, -1); Len++; quiry[j].y = L;
        }
        for(int j = 0; j < mid.size(); j++) Tr1add(mid[j], 1);
        i = Now;
    }
    sort(quiry+1, quiry+1+Q, cmp2);
    int Len = N;
    for(int i = 1; i <= Q; i++){
        int ans;
        if(!quiry[i].vis){
            if(quiry[i].y < M) ans = (quiry[i].x-1)*M+quiry[i].y, printf("%lld\n", ans);
            else{
                quiry[i].y -= M; ans = Extra[quiry[i].x][quiry[i].y];
                printf("%lld\n", ans);
            }
        }
        int L = 1, R = Len;
        while(R > L){
            int MID = (R+L) / 2;
            if(Tr2qui(MID) >= quiry[i].x) R = MID;
            else L = MID+1;
        }
        Tr2add(L, -1);
        if(quiry[i].vis) ans = last[L], printf("%lld\n", ans);
        else Extra[quiry[i].x].push_back(last[L]);
        last[++Len] = ans;
    }
end:
    cerr << "Time Used: " << clock() - c1 << "ms" << endl;
    return 0;
}






__EOF__

        

        

            

                report
            

        

    







        
Recommend

        



                

    
About Joyk

    
 





Aggregate valuable and interesting links.

Joyk means Joy of geeK