首页 > 其他分享 >树状数组浅谈

树状数组浅谈

时间：2024-09-22 16:45:25浏览次数：10  
标签：... 浅谈 树状 int lowbit 查询 数组

什么是树状数组

树状数组是一种码量小，常数小，支持单点修改和区间查询的数据结构。

树状数组维护的信息和运算需要满足结合律并且可差分

注意gcd和max操作虽然满足结合律，但不可差分，因此不能使用树状数组维护

其实，树状数组能做的，线段树都能做，线段树能做的，树状数组不一定能做，但线段树码量大，常数大，不像树状数组，码量小，常数小, 适合我这种懒人使用。因此还是要学的，毕竟谁都不想再考场上手打一个线段树。

进过一些操作后树状数组也可以支持区间查询和单点修改，这个我们待会再说。

如何实现

引入

让我们先来看一个问题：

给定一个序列，满足以下操作

  1. 将某一个数加上一个值
  2. 查询 \(l\) 到 \(r\) 的和

假设你还没学过线段树和树状数组，你会怎么做这道题。

显然有两种方法

方法1：直接模拟，修改 \(O(1)\) ，查询 \(O(n)\)

方法2：前缀和，修改 \(O(n)\)，查询 \(O(1)\)

然而，如果操作次数很多序列又很长的话上面的做法就显得有些无力了，这时我们就需要使用树状数组来解决这个问题。

树状数组计算 \(a_1+a_2+a_3+a_4+...+a_n\) 是把它们拆成不超过 \(\log n\) 段进行计算，这样我们只需要合并 \(\log n\) 段区间就能够计算出结果，相比于暴力效率有很大的提高。下面是一张简图，生动的展示了树状数组的工作原理。

114514

最下面的八个方块表示原始数组，上面的方块就是c数组，用来存放某一段区间的和, 这些信息是已知的，我们可以把前缀和拆成这些小区间来计算。

从图中可以看出，\(c[i]\) 存的是以 \(i\) 为右端点的一段区间的和，让我们先不管左端点，来感受一下树状数组是如何查询的。

例如我们要查询 \([1,7]\) 的区间和。就会从\(c[7]\) 开始跳，先将答案加上 \(c[7]\) ，发现 \(c[7]\) 计算的是 \([7, 7]\) 的和，于是我们跳到 \(c[6]\)，发现 \(c[6]\) 算的是 \([5,6]\) 的和，所以我们跳到 \(c[4]\)，并将答案加上 \(c[6]\)。\(c[4]\) 算的是 \([1,4]\) 的和，我们将答案加上 \(c[4]\)，但此时前面已经没有可跳了，所以过程结束，返回答案。

如果我们要查询 \([4, 7]\) 的和怎么办呢，我们可以利用前缀和的思想，用 \([1,7]\) 的和减去 \([1,3]\) 的和就好了。

区间大小

现在我们来考虑左端点在哪里。

在树状数组中，我们规定 \(c_x\) 的存的是 \([x-\operatorname{lowbit}(x)+1, x]\) 的和。\(\operatorname{lowbit}(x)\) 指的是 \(x\) 这个数在二进制下最低位的1的位权。

我们要如何计算 \(\operatorname{lowbit}(x)\) 呢。根据位运算知识得，\(\operatorname{lowbit}(x) = x\ \& -x\)，有人肯定要问，为什么？ 下面是一段摘自oiwiki的解释，可能可以帮助理解。

将 x 的二进制所有位全部取反，再加 1，就可以得到 -x 的二进制编码。例如，6 的二进制编码是 110，全部取反后得到 001，加 1 得到 010。

设原先 x 的二进制编码是 (...)10...00，全部取反后得到 [...]01...11，加 1 后得到 [...]10...00，也就是 -x 的二进制编码了。这里 x 二进制表示中第一个 1 是 x 最低位的 1。

(...) 和 [...] 中省略号的每一位分别相反，所以 x & -x = (...)10...00 & [...]10...00 = 10...00，得到的结果就是 \(\operatorname{lowbit}\)。

代码实现：

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

区间查询

回顾一下刚才举的例子，不难想出查询前缀和的方法，我们写出计算 \([1, x]\) 的和的过程。

  1. 将 \(ans\) 加上 \(c_x\)
  2. \(x\) 减去 \(\operatorname{lowbit}(x)\)
  3. 判断 \(x\) 是否为 \(0\) ，不是就回到第1步，否则返回 \(ans\)

代码实现：

int sum(int x){
    int res = 0;
    while(x){
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

那么我们可以写出查询 \([l, r]\) 区间和的代码

int query(int l, int r){
    return sum(r) - sum(l-1);
}

区间查询部分完结。

单点修改

修改一个值其实只需要把管辖了 \(a_x\) 的 \(c_y\) 找到并修改即可，那我们怎么找到管辖了 \(a_x\) 的 \(c_y\) 呢？

显而易见的，\(c_x\) 管辖了 \(a_x\)。在之前的那副简图中可以看出 \(c[x]\) 被 \(c[x+\operatorname{lowbit}(x)]\) 包含。

于是我们就有了一种找的方法，假设要把 \(a_x\) 加上 \(y\)， 下面给出过程。

  1. 将 \(c_x\) 加上 \(a_x\)。
  2. \(x\) 加上 \(\operatorname{lowbit}(x)\)
  3. 如果 \(x\) 大于 \(n\) 那么退出，否则回到第1步。

代码如下：

void modify(int x, int y){
    while(x <= n){
        c[x] += y;
        x += lowbit(x);
    }
}

建树

可以直接转换为 \(n\) 次单点修改。

代码如下：

for(int i = 1; i <= n; i++){
    int x;
    scanf("%d", &x);
    modify(i, x);
}

完整代码

#include<bits/stdc++.h>
using namespace std;
int n, m, c[1000010];
int lowbit(int x){
    return x & (-x);
}
void modify(int x, int y){
    while(x <= n){
        c[x] += y;
        x += lowbit(x);
    }
}
int sum(int x){
    int res = 0;
    while(x >= 1){
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}
int query(int l, int r){
    return sum(r) - sum(l-1);
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        int x;
        scanf("%d", &x);
        modify(i, x);
    }
    for(int i = 1; i <= m; i++){
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if(opt == 1){
            modify(x, y);
        }else{
            printf("%d\n", query(x, y));
        }
    }
    return 0;
}

好了，你已经学会了基础的树状数组，接着我们来学习如何让树状数组支持区间修改单点查询

区间修改单点查询

题目：【模板】树状数组 2

我们发现如果树状数组维护的是原本的数组则无法实现，考虑维护差分数组。

我们知道在如果要将 \([l, r]\) 的所有数加上 \(x\) 的话，只需要在差分数组的第 \(l\) 位加上 \(x\)，再在第 \(r+1\) 位减去 \(x\) 即可。

而查询第 \(x\) 个数是多少其实就是计算差分数组前 \(x\) 个数的和。这两个操作树状数组都可以实现，于是我们就做完了。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n, m, a[1000010], b[1000010], c[1000010];
int lowbit(int x){
	return x & (-x);
}
void modify(int x, int y){
	for(int i = x; i <= n; i += lowbit(i)){
		c[i] += y;
	}
	return ;
}
int query(int x){
	int res = 0;
	for(int i = x; i; i -= lowbit(i)){
		res += c[i];
	}
	return res;
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		b[i] = a[i] - a[i-1];
		modify(i, b[i]);
	}
	while(m--){
		int opt;
		scanf("%d", &opt);
		if(opt == 1){
			int l, r, x;
			scanf("%d%d%d", &l, &r, &x);
			modify(l, x);
			modify(r+1, -x);
		}else if(opt == 2){
			int p;
			scanf("%d", &p);
			printf("%d\n", query(p));
		}
	}
	return 0;
}

好了，现在你已经学会了基本的树状数组，来做几道例题吧

例题

例题1：[CQOI2006] 简单题

题目链接

这是一道树状数组板子题，只需要把区间修改单点查询的加法改为异或就好了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, m, c[100001];
int lowbit(int x){
	return x & (-x);
}
void add(int x){
	for(int i = x; i <= n; i += lowbit(i)){
		c[i] ^= 1;
	}
}
int sum(int x){
	int res = 0;
	for(int i = x; i; i -= lowbit(i)){
		res ^= c[i];
	}
	return res;
}
int main(){
	scanf("%d%d", &n, &m);
	while(m--){
		int opt, l, r;
		scanf("%d%d", &opt, &l);
		if(opt == 1){
			scanf("%d", &r);
			add(l);
			add(r+1);
		}else{
			printf("%d\n", sum(l));
		}
	}
	return 0;
}

例题2：HH的项链

题目链接

首先，如果一个贝壳反复出现，那我们只要关注它出现的某一个位置而忽略其他位置，显而易见的，我们可以关注最右边的位置，因为好更新。

既然关注右边的贝壳，那么我们就要从左到右的处理数组，注意到这题不强制在线，于是我们可以离线后按照右端点排序，这样保证了右边的数是按顺序更新的。

查询的时候利用前缀和思想即可。

下面引入一个数组 \(vis\)。\(vis_i\) 表示第 \(i\) 种贝壳在目前询问的区间内最后出现的位置。还有一个名叫 \(last\) 的变量，意思是还没修改区间的左端点，每次更新从它开始。

我们写出修改部分的代码：

    int last = 1;
    for(int i = 1; i <= m; i++){
        for(int j = last; j <= q[i].r; j++){
            if(vis[a[j]]) modify(vis[a[j]], -1);//如果之前有这个数就先把它删掉
            modify(j, 1);//用新的位置代替
            vis[a[j]] = j;//修改vis数组
        }
        last = q[i].r+1;//更新last
        ans[q[i].id] = query(q[i].r) - query(q[i].l-1);
    }

总代码，可以配合理解：

#include<bits/stdc++.h>
using namespace std;
namespace qwq{
	inline int read(){
		int n = 0;  
		int f = 1;
		char c = getchar();
		while(c < '0' || c > '9'){
			if(c == '-') f = -1;
			c = getchar();
		}
		while(c >= '0' && c <= '9'){
			n = (n << 3) + (n << 1) + (c ^ 48);
			c = getchar();
		}
		return n * f;
	}
	inline void Write(int x){
		if(x < 0){
			putchar('-');
			x = -x;
		}
		if(x > 9) Write(x / 10);
		putchar((x % 10) ^ 48);
		return;
	}
	inline void write(int x, char c){
		Write(x);
		putchar(c);
	}
}
using namespace qwq;
struct node{
    int l, r, id;
    bool operator < (const node &A){
        return r < A.r;
    }
} q[1000010];
int tree[1000010], n, m, a[1000010], vis[1000010], ans[1000010];
int lowbit(int x){
    return x & (-x);
}
void modify(int x, int y){
    while(x <= n){
        tree[x] += y;
        x += lowbit(x);
    }
}
int query(int x){
    int res = 0;
    while(x){
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}
int main(){
    n = read();
    for(int i = 1; i <= n; i++){
        a[i] = read();
    }
    m = read();
    for(int i = 1; i <= m; i++){
        q[i].l = read(), q[i].r = read(), q[i].id = i;
    }
    sort(q+1, q+m+1);
    int last = 1;
    for(int i = 1; i <= m; i++){
        for(int j = last; j <= q[i].r; j++){
            if(vis[a[j]]) modify(vis[a[j]], -1);
            modify(j, 1);
            vis[a[j]] = j;
        }
        last = q[i].r+1;
        ans[q[i].id] = query(q[i].r) - query(q[i].l-1);
    }
    for(int i = 1; i <= m; i++){
        write(ans[i], '\n');
    }
    return 0;
}

这道题还有一个莫队做法，感兴趣的读者可自行了解。

结语

上面就是我的总结和笔记，这里其实还有很多技巧没有讲到，例如扫描线等，之后可能会补充。还有树状数组虽然代码短，但适用范围小，线段树还是要学的。让我们一起，向着神犇的路进发。

标签：...,浅谈,树状,int,lowbit,查询,数组
From： https://www.cnblogs.com/jrzhr/p/18425506

相关文章

  • 浅谈在.Net Framework Winforms程序中调用 WinRT API
    浅谈在.NetFramework桌面应用中调用WinRTAPI【作者:张赐荣】在开发Windows程序时，我们经常会遇到需要调用系统功能的场景，比如文件操作、录音、摄像头管理等。在传统的桌面应用开发中，使用.NetFramework封装的Win32API**或者直接调用底层复杂的com接口来完成这些功能，......
  • C++速通LeetCode中等第10题-轮转数组（四种方法）
    方法一：巧用deque双向队列容器classSolution{public:voidrotate(vector<int>&nums,intk){deque<int>q;inttmp;if(nums.size()>1){for(autonum:nums)q.push_back(num);......
  • 浅谈金融科技十大发展趋势
    当前，新一轮科技革命和产业变革深入发展，正在加快生产力和生产关系变革。金融科技作为技术驱动的金融创新，在银行发展全局中的地位和作用将愈发凸显。银行业要努力探寻金融科技发展的根本规律和发展趋势，不断掌握新技术、新技能，创新应用新方法、新工具，充分发挥科技创新的战略先导地......
  • C++：数组与字符串
    一、数组         数组是一种存储若干元素的数据类型，在诸多编程语言中存在，其显著的特点是元素通常是在物理层面上连续存储的（逻辑上的数组，比如链表，可能不是），并且具有极快的元素访问速度。    数组通常是同构的（homogenous ），即数组中的元素都是同一类型的，......
  • Leetcode 2464. 有效分割中的最少子数组数目
    1.题目基本信息1.1.题目描述给定一个整数数组nums。如果要将整数数组nums拆分为子数组后是有效的，则必须满足:每个子数组的第一个和最后一个元素的最大公约数大于1，且nums的每个元素只属于一个子数组。返回nums的有效子数组拆分中的最少子数组数目。如果不能进......
  • 返回数组中的最大元素个数
    /***返回数组中的最大元素个数*约束：*数组大小1<=size<=10to5*数组元素大小1<=arrList[i]<=10to7*@paramcandles*@return*/publicstaticintbirthdayCakeCandles(List<Integer>candles){if(cand......
  • 【信号传输】DMA传输只能收到一半数据，发送123456 只能收到 123， 发送abcd只能收到ab，缓
    系列文章目录1.元件基础2.电路设计3.PCB设计4.元件焊接5.板子调试6.程序设计7.算法学习8.编写exe9.检测标准10.项目举例11.职业规划文章目录方案一、改DMA中断方案二、改数据类型方案三、改数据长度后记方案一、改DMA中断每个DMA通道都可以在DMA传......
  • 每日一题--交换数组
    题目【一维数组】交换数组作业内容将数组A中的内容和数组B中的内容进行交换。（数组一样大）答案#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>intmain(){ inta=0,b=0,c=0; intarr1[3]={1,2,3}; intarr2[3]={4,5,6}; intsz=sizeof(a......
  • python怎么初始化数组
    因为画图中x轴与y轴的数据通常为数组格式的数据，所以先总结一下如何初始化数组：（1）list得到数组# 通过array函数传递list对象L = [1, 2, 3, 4, 5, 6]a = np.array(L)# 若传递的是多层嵌套的list，将创建多维数组b = np.array([[1, 2, 3, 4], [5, 6, 7, ......
  • 【C++】数组案例：考试成绩统计
    要求：一个简单的二维数组使用案例，用于统计三个学生在三门课程中的考试成绩总分。代码要点：二维数组声明和初始化：intscore[3][3]：声明一个3行3列的二维数组，用于存储三个学生的三门课程成绩。初始化列表：为数组的每个元素赋初始值。总分统计：外层循环：遍历每个学生（行）。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99