论坛 › 物联网 › 数据布局与算法-数据布局-树状数组

玛卡巴卡的卡巴卡玛 发表于 2025-3-28 00:28:52

数据布局与算法-数据布局-树状数组

概念

树状数组，也叫二叉索引树（Binary Indexed Tree，BIT），它是用数组来模拟树形布局。树状数组的每个节点存储的是数组中某一段的和（或其他可合并的信息），通过巧妙的索引方式和树形布局，能够在对数时间内完成前缀和的查询以及单个元素的修改操纵。
原理
布局特点：树状数组的布局基于二进制位的原理。对于一个数组 C，假设其下标从 1 开始，对于任意下标 i，C 负责维护的区间长度是 i 的二进制表示中最低位的 1 所对应的值。比方，i = 6，二进制表示为 110，最低位的 1 对应的值是 2，所以 C 维护的区间长度为 2，即 C 存储的是 a + a 的和（假设 a 是原始数组）。
前缀和盘算：盘算前缀和时，利用树状数组的布局特点，通过不绝地访问父节点来累加区间和。比方，要求 a 到 a 的前缀和，7 的二进制是 111，则依次访问 C、C、C 并累加它们的值，就能得到前缀和。这是因为 C 包含了 a，C 包含了 a + a，C 包含了 a + a + a + a，恰好覆盖了 a 到 a 的范围。
单点更新：当对原始数组中的一个元素举行修改时，必要更新树状数组中与之相关的节点。比方，修改 a 的值，那么必要更新所有包含 a 的区间对应的树状数组节点。通过不绝地将 i 加上其最低位的 1 来找到必要更新的节点。比方，i = 3，二进制是 11，更新完 C 后，下一个要更新的是 C，因为 3 加上最低位的 1（即 1）得到 4，以此类推，直到超出数组范围。
处置惩罚的问题范例
前缀和查询：快速盘算数组中某一段的前缀和，时间复杂度为 O(logn)，相比朴素的遍历求和方法（时间复杂度为 O(n)）效率更高。
单点更新：在修改数组中单个元素的值后，能够快速更新相关的前缀和信息，同样具有 O(logn) 的时间复杂度。
区间修改和查询：通过一些技巧，可以将树状数组扩展到支持区间修改和区间查询操纵。比方，利用差分头脑，将区间修改转化为单点修改，然后再通过树状数组来维护差分后的数组，从而实现高效的区间操纵。

注意：假如数据满足差分的条件，也可以实现区间更新以及区间查询
一些步骤，功能

1，lowbit
lowbit 函数用于获取一个整数二进制表示中最低位的 1 所对应的值。比方，对于数字 6，它的二进制表示是 110，最低位的 1 对应的值是 2；对于数字 7，二进制表示是 111，最低位的 1 对应的值是 1。在树状数组里，lowbit 至关重要，它能帮助我们快速找到节点之间的父子关系。
代码：
int lowbit(int x) {
    return x & -x;}
2，get_sum
get_sum 函数用于盘算树状数组中前 i 个元素的前缀和。它利用树状数组的布局特点，通过不绝访问父节点并累加区间和来实现前缀和的快速盘算。
int get_sum(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree;
            i -= lowbit(i);
        }
        return sum;
    }
3,update
update 函数用于更新树状数组中第 i 个元素的值。当修改原始数组中的某个元素时，必要更新树状数组中所有包含该元素的区间节点，以包管前缀和信息的精确性。
void update(int i, int val) {
     while (i <= n) {
         tree += val;
         i += lowbit(i);
    }
}
4,初始化O(n)的初始化
-利用前缀和的初始化，先盘算a的前缀和数组pre，然后根据c=pre-pre来盘算
for (int i = 1; i <= n; ++i) {
            prefixSum = prefixSum + arr;
        }

        // 初始化树状数组
        for (int i = 1; i <= n; ++i) {
            tree = prefixSum - prefixSum;
        }

-利用update做到原地的O(n)的修改
void init() {
 for (int i = 1; i <= n; ++i) {
t += a;
int j = i + lowbit(i);
 if (j <= n) t += t;
}
 }


练习题：

楼兰图腾

在完成了分配任务之后，西部 314 来到了楼兰古城的西部。相传好久从前这片土地上（比楼兰古城还早）生活着两个部落，一个部落崇拜尖刀（V），一个部落崇拜铁锹（∧），他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。
西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 N 个点，经测量发现这 N 个点的水平位置和竖直位置是两两不同的。西部 314 认为这幅壁画所包含的信息与这 N 个点的相对位置有关，因此不妨设坐标分别为 (1,y1​),(2,y2​),⋯,(n,yn​)，此中 y1​∼yn​ 是 1 到 n 的一个分列。
https://i-blog.csdnimg.cn/direct/847c0ffb77284379b389cf7e8dc51729.png
如图，图中的 y1​=1，y2​=5，y3​=3，y4​=2，y5​=4。
西部 314 打算研究这幅壁画中包含着多少个图腾，此中 V 图腾的定义如下（注意：图腾的情势只和这三个纵坐标的相对巨细分列顺序有关）1≤i<j<k≤n 且 yi​>yj​, yj​<yk​；
而崇拜 ∧ 的部落的图腾被定义为 1≤i<j<k≤n 且 yi​<yj​，yj​>yk​；
西部 314 想知道，这 n 个点中两个部落图腾的数目。因此，你必要编写一个步伐来求出 V 的个数和 ∧ 的个数。
输入格式
第一行一个正整数 n；
第二行是 n 个正整数，分别代表 y1​,y2​,⋯,yn​。
输特别式
输出两个数，中间用空格隔开，依次为 V 的个数和 ∧ 的个数
分析，很裸的树状数组，统计前后的比当前值大的，小的值的数，根据乘法原理，得答案
代码：




#include <iostream>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;

const int N = 200010;
int n;
int c, a;

// 盘算 x 的最低位 1 代表的值
int lb(int x) {
    return x & -x;
}

// 查询前缀和
long long get(int x) {
    long long res = 0;
    for (int i = x; i; i -= lb(i)) res += c;
    return res;
}

// 更新树状数组
void up(int x, int val) {
    for (int i = x; i <=n; i += lb(i)) {
        c += val;
    }
}

long long preg, prel;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a;

    for (int i = 1; i <= n; i++) {
        preg = get(n) - get(a);
        prel = get(a - 1);
        up(a, 1);
    }

    long long res1 = 0, res2 = 0;
    memset(c, 0, sizeof c);
    for (int i = n; i; i--) {
        res1 += preg * (get(n) - get(a));
        res2 += prel * get(a - 1);
        up(a, 1);
    }

    cout << res1 << ' ' << res2 << endl;
    return 0;
}



一个简单的整数问题

给定长度为 NN 的数列 AA，然后输入 MM 行操纵指令。
第一类指令形如 C l r d，表示把数列中第 l∼rl∼r 个数都加 dd。
第二类指令形如 Q x，表示扣问数列中第 xx 个数的值。
对于每个扣问，输出一个整数表示答案。
输入格式
第一行包含两个整数 NN 和 MM。
第二行包含 NN 个整数 AA。
接下来 MM 行表示 MM 条指令，每条指令的格式如标题描述所示。
输特别式
对于每个扣问，输出一个整数表示答案。
每个答案占一行。
分析：
内核是一个单点查询和区间修改的题，我们可以通过差分和树状数组的合作来解决

代码：

#include <iostream>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;

const int N = 200010;
int n,m;
int c, a;

// 盘算 x 的最低位 1 代表的值
int lb(int x) {
    return x & -x;
}

// 查询前缀和
long long get(int x) {
    long long res = 0;
    for (int i = x; i; i -= lb(i)) res += c;
    return res;
}

// 更新树状数组
void up(int x, int val) {
    for (int i = x; i <=n; i += lb(i)) {
        c += val;
    }
}


int main() {
    cin >> n>>m;
    for (int i = 1; i <= n; i++) cin >> a;

    for (int i = 1; i <= n; i++) {
        up(i, a-a);
    }
    for(int i=0;i<m;i++){
        char w;
        cin>>w;
        if(w=='Q'){
            int tmp;
            scanf("%d",&tmp);
            cout<<get(tmp)<<endl;
        }else {
            int l,r,d;
            scanf("%d%d%d",&l,&r,&d);
            up(l,d);
            up(r+1,-d);
        }
        
    }

    return 0;
}
一个简单的整数问题2：




给定一个长度为 NN 的数列 AA，以及 MM 条指令，每条指令可能是以下两种之一：
C l r d，表示把 A,A,…,AA,A,…,A 都加上 dd。
Q l r，表示扣问数列中第 l∼rl∼r 个数的和。
对于每个扣问，输出一个整数表示答案。
输入格式
第一行两个整数 N,MN,M。
第二行 NN 个整数 AA。
接下来 MM 行表示 MM 条指令，每条指令的格式如标题描述所示。
输特别式
对于每个扣问，输出一个整数表示答案。
每个答案占一行。

分析：


内核是区间查询和区间修改，上面的区间修改利用了差分来解决，接下来的区间查询可以根据贡献度来帮忙处置惩罚
先明确下get_sum的作用，我们想要他求出1~i的数字的和，那么对于区间l~r，就可以通过调用get(r)-get(l-1)来得到答案
接下来的问题就是怎样实现get_sum，我们先看看我的之前的get（x）的作用，是求出第x个数字的巨细。我们通过下面的操纵
https://i-blog.csdnimg.cn/direct/1f23c07a56284d25b847a68957842a2b.png
发现了黑色的d对于我们黑色部分的贡献度是i*d，我们的目标是
aim =（n+1）*get(n)-∑i*d，
我们不妨用一个树状数组来存储一下这个i*d，那么我们的aim
aim=（n+1）*get(n,原来的树状数组) -get(n,i*d的树状数组)
代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 200010;
long long n, m;
long long c, a, ci;

// 盘算 x 的最低位 1 代表的值
long long lb(long long x) {
    return x & -x;
}

// 查询前缀和
long long get(long long x, long long w[]) {
    long long res = 0;
    for (int i = x; i; i -= lb(i)) res += w;
    return res;
}

// 更新树状数组
void up(long long x, long long val, long long w[]) {
    for (int i = x; i < N; i += lb(i)) {
        w += val;
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a);

    for (int i = 1; i <= n; i++) {
        up(i, a - a, c);
        up(i, i * (a - a), ci);
    }

    for (int i = 0; i < m; i++) {
        char w;
        scanf(" %c", &w);  // 注意这里的空格，用于消耗掉之前输入的换行符
        if (w == 'Q') {
            int l,r;
            scanf("%d%d", &l,&r);
            long long rr=get(r, c) * (r + 1) - get(r, ci);
            long long ll=get(l-1, c) * (l ) - get(l-1, ci);
            printf("%lld\n", rr-ll);
        } else {
            int l, r, d;
            scanf("%d %d %d", &l, &r, &d);
            up(l, d, c);
            up(r + 1, -d, c);
            up(l, l * d, ci);
            up(r + 1, -(r + 1)*d , ci);
        }
    }

    return 0;
}  

谜一样的牛：

有 nn 头奶牛，已知它们的身高为 1∼n1∼n 且各不相同，但不知道每头奶牛的具体身高。
如今这 nn 头奶牛站成一列，已知第 ii 头牛前面有 AiAi 头牛比它低，求每头奶牛的身高。
输入格式
第 11 行：输入整数 nn。
第 2..n2..n 行：每行输入一个整数 AiAi，第 ii 行表示第 ii 头牛前面有 AiAi 头牛比它低。
（注意：因为第 11 头牛前面没有牛，所以并没有将它列出）
输特别式
输出包含 nn 行，每行输出一个整数表示牛的身高。
第 ii 行输出第 ii 头牛的身高。

分析：

二分+树状数组，从后面向前遍历，通过二分找到第k大的数，然后记载答案即可，假如不会二分也可以用两个优先队列，然后从一个里面pop出来k个，放到另外一个，然后取到第k大的后，都放在一个队列里面，如此往复

代码：


#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a;
int ans;
int tr;

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i)) tr += c;
}

int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr;
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 2; i <= n; i ++ ) scanf("%d", &a);
    for (int i = 1; i <= n; i ++ ) add(i,1);
    for (int i = n; i; i -- )
    {
        int k = a + 1;
        int l = 1, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (sum(mid) >= k) r = mid;
            else l = mid + 1;
        }
        ans = r;
        add(r, -1);     //删除
    }

    for (int i = 1; i <= n; i ++ ) printf("%d\n", ans);

    return 0;
}


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

查看完整版本: 数据布局与算法-数据布局-树状数组