Chapter8——基础算法——树状数组

1. lowbit运算

lowbit(x)=x\&(-x)
就是取x的二进制最右边的1和它右边所有的0组成的二进制数。

2. 树状数组

应用于区间求和、求数组的中位数、第k大、第k小、求逆序对等问题。

树状数组是用来记录和的数组,只不过它存放的不是前i个整数的和,而是在i号位之前(含i号位)lowbit(i)个整数的和。

image.png

使用树状数组可以在O(\log n)时间复杂度实现动态更新求和操作

const int maxk = 100010; // hash key 的最大值
int c[maxk]; // 树状数组,从下标1开始存储
void update(int x, int v){ // 将第x个整数加上v
    for (int i = x; i <= maxk; i += lowbit(i))
        c[i] += v;
}

int getSum(int x){ // 返回前x个整数和
    int sum = 0;
    for (int i =x; i > 0; i -= lowbit(i))
        sum += c[i];
    return sum;
}

3. 例子

3.1 求序列第k小的数

给定一个N个正整数的序列A(N\le 10^{5},A[i]\le 10^{5}),求A中第k小的数。

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define lowbit(x) ((x)&(-x))
using namespace std;
/*
    树状数组应用于求前i个元素的和,并且适用于动态更新
    查询和更新的时间复杂度均为O(logn)
    
    本例是求数组中每个元素的左边比他小的元素个数
    如{1,5,3,2,6},元素个数{0,1,1,1,4}
    
    使用hash存储每个数的个数,对于5来说,只要求
    hash[1] + hash[2] + ... + hash[4]的和,
    求和使用树状数组 
*/
const int maxn = 100010;
int c[maxn];

void update(int x, int v){ 
    // 覆盖x的树状数组加上v
    for (int i = x; i <= maxn; i += lowbit(i)){
        c[i] += v;
    } 
}

int getSum(int x){
    // 获取前x的序列和
    // 树状数组从1开始 
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)){
        sum += c[i];
    } 
    return sum;
}

int binarySearch(int l, int r, int x){
    while (l < x){
        int mid = (l + r) / 2;
        if (x <= getSum(mid)) // getSum(i)返回比i小的序列个数 
            r = mid;
        else l = mid + 1;
    }
    return l;
} 

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    memset(c, 0, sizeof(c));
    int x;
    for (int i = 0; i < n; i++){
        scanf("%d", &x);
        update(x, 1); // 更新覆盖v的所有树状数组 
    } 
    // 找到第k小 
    printf("%d\n", binarySearch(1, maxn, k));
    return 0; 
}

3.2 离散化过大的key

现给定一个序列A位[520, 99999999, 18, 666, 8888],那么树状数组会开到999999999的大小,显然超内存。那么这时如何找到数组A的第k小的数呢? 由于只需要考虑相对大小,那么可以设置一个临时的结构体数组,用以存放输入的序列元素的值和原始序号,输入完成后将数组按val从小到大排序,排序完再按照“计算排名的方式”将排名根据原始序号存入到一个新的数组即可。
从而将原始的高值数组映射位低值的排名数组

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lowbit(i) ((i) & (-i))
using namespace std;
/*
    当使用树状数组时,遇到hash的key过大,超出内存空间,
    怎么办?
    
    如果问题只关心大小的关系(排名)的话,而不关心具体
    数值,那么可以把hash的key进行排名,将原始数值key映射
    为rank排名,再利用树状数组求和操作。
    
    紧接leftSum.cpp的例子,若输入数组:
    {999999999, 18, 18, 66, 55}
*/
const int maxn = 100010;
struct Node{
    int val;
    int pos;
} temp[maxn], origin[maxn]; // 记录第i个数的数值和下标对应关系 
int c[maxn]; //树状数组
int a[maxn]; //排名数组 a[i]= rank(i),记录第i个数的排名,排名从1开始 

int cmp(Node n1, Node n2){
    return n1.val < n2.val;
}

void update(int x, int v){
    for (int i = x; i <= maxn; i += lowbit(i))
        c[i] += v;  
}

int getSum(int x){
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) // 从1开始的lowbit 
        sum += c[i];
    return sum;
}

int binarySearch(int l, int r, int x){
    while (l < x){
        int mid = (l + r) / 2;
        if (x <= getSum(mid)) // getSum(i)返回比i小的序列个数 
            r = mid;
        else l = mid + 1;
    }
    return l;
} 

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++){
        scanf("%d", &temp[i].val);
        temp[i].pos = i;
        origin[i] = temp[i];
    }
    sort(temp, temp + n, cmp);
    for (int i = 0; i < n; i++){
        if (i == 0 || temp[i].val != temp[i - 1].val )
            a[temp[i].pos] = i + 1; //排名从1开始 
        else
            a[temp[i].pos] = a[temp[i - 1].pos]; // 排名与前一名一样 
    }
    for (int i = 0; i < n; i++){
        update(a[i], 1); // 更新覆盖v的所有树状数组 
    }
    int rank = binarySearch(1, maxn, k);
    for (int i = 0; i < n; i++)
        if (a[i] == rank){ // i是数的下标 
            printf("%d\n", origin[i].val);
            break;
        }
    return 0;
} 

3.3 寻找中位数 ——PAT1057 Stack

3.3.1 题目描述

Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian -- return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th if N is odd.

Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤10
​5
​​ ). Then N lines follow, each contains a command in one of the following 3 formats:

Push key
Pop
PeekMedian
where key is a positive integer no more than 10
​5
​​ .

Output Specification:
For each Push command, insert key into the stack and output nothing. For each Pop or PeekMedian command, print in a line the corresponding returned value. If the command is invalid, print Invalid instead.

Sample Input:
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop
Sample Output:
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

3.3.2 解决思路

求动态变化的数组中位数,使用树状数组求解,包含以下三个树状数组的核心操作

  • Push x:update(x, 1)
  • Pop: update(top, -1)
  • PeekMedian:binarySearch(0, maxk, (N + 1) / 2)

3.3.3 代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#define lowbit(i) ((i) &(-i))
using namespace std;

const int maxn = 100010;
const int maxk = 100010;
int c[maxk];
char op[15];
stack<int> sk;

void update(int x, int v){
    for (int i = x; i <= maxk; i += lowbit(i))
        c[i] += v;
}

int getSum(int x){
    int sum = 0;
    for (int i =x; i > 0; i -= lowbit(i))
        sum += c[i];
    return sum;
}

int binarySearch(int l, int r, int x){ // 二分搜索x 
    while (l < r){
        int mid = (l + r) / 2; 
        if (getSum(mid) >= x) r = mid; 
        else l = mid + 1;
    }
    return l;
}

int main(){
    int n;
    scanf("%d", &n);
    memset(c, 0, sizeof(c));
    for (int i = 0; i < n; i++){
        scanf("%s", op);
        if (strcmp(op, "Pop") == 0){
            if (sk.empty())
                printf("Invalid\n");
            else{
                int top = sk.top();
                printf("%d\n", top);
                update(top, -1);
                sk.pop();
            }
        }else if (strcmp(op, "Push") == 0){
            int e;
            scanf("%d", &e);
            update(e, 1);
            sk.push(e);
        } else if (strcmp(op, "PeekMedian") == 0){
            if (sk.empty()){
                printf("Invalid\n");
            }else{
                // 如果栈内元素个数为奇数
                int size = sk.size();
                int index; // 排过序后的Median元素下标 
                if (size % 2)
                    index = (size + 1) / 2;
                else 
                    index = size / 2;
                // 由于getSum(i)是递增的,所以使用二分搜索Median值
                int median = binarySearch(1, maxn, index); 
                printf("%d\n", median);
            }
        }
    }
} 

3.4 二维树状数组——POJ2155 Matrix

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,098评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,213评论 2 380
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,960评论 0 336
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,519评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,512评论 5 364
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,533评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,914评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,574评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,804评论 1 296
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,563评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,644评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,350评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,933评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,908评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,146评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,847评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,361评论 2 342

推荐阅读更多精彩内容