基础的树状数组、线段树操作（区间求和，单点修改、区间修改） |
您所在的位置：网站首页 › 线段树区间求和 › 基础的树状数组、线段树操作（区间求和，单点修改、区间修改） |
基础的树状数组、线段树操作（区间求和，单点修改、区间修改）
|
目录 动态求连续区间和 所以用到另一种方法——树状数组 另一种方法——线段树 完整线段树代码
数列区间最大值 分析： 具体实现： 数星星 小朋友排队 分析： 代码实现（树状数组）： 一个简单的整数问题2 改进 代码实现 动态求连续区间和 给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b][a,b] 的连续和。 输入格式 第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。 第二行包含 n 个整数，表示完整数列。 接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。 数列从 1 开始计数。 输出格式 输出若干行数字，表示 k=0 时，对应的子数列 [a,b] 的连续和。 数据范围 1≤n≤100000, 1≤m≤100000， 1≤a≤b≤n, 数据保证在任何时候，数列中所有元素之和均在 int 范围内。 输入样例： 10 5 1 2 3 4 5 6 7 8 9 10 1 1 5 0 1 3 0 4 8 1 7 5 0 4 8
输出样例： 11 30 35
1264. 动态求连续区间和 - AcWing题库 对于求区间问题，最先想到的应该是前缀和 建立一个前缀和数组 区间查询：O（1） 元素修改：O（n）显然元素修改可能存在过于复杂的情况 所以用到另一种方法——树状数组 区间查询：O（log n） 元素修改：O（log n）在讲具体算法前，要先介绍一个具体的操作 lowbit运算——找出一个数二进制的最低位1（例如9：1001 -> 1 12：1100 -> 100） 设数为x，x按位取反，设为~x x 按位与 ~x为0，当x按位与（~x+1）时，得到结果 计算机内的数字按照补码规则，负数的补码与对应正数的反码加一相等，所以简化为x & -x 以lowbit运算为基础，构建一个树状数组 编辑
元素修改 void add(int x,int w){ for(int i = x;i 0;i -= lowbit(i)){ res += t[i]; } return res; }
实现这两个功能之后，就可以写出代码了 #include #include #include using namespace std; const int N = 1e5+10; int t[N]; int n,m; int lowbit(int x) // 返回末尾的1 { return x & -x; //正数的反码加一等于补码，即对应负数 } void add(int x,int w){ for(int i = x;i 0;i -= lowbit(i)){ //找到u之前所有的子节点，输出累加和 res += t[i]; } return res; } int main() { cin >> n >> m; for (int i = 1; i > t; add(i,t); //初始化数组 } for(int i = 1;i > k >> a >> b; if(k == 1){ add(a,b); //元素修改 }else{ cout > a >> b; if(k){ add(1,a,b); }else{ printf("%d\n",query(1,a,b)); } } }
另一道与线段树相关的题目：1270. 数列区间最大值 - AcWing题库 数列区间最大值输入一串数字，给你 M 个询问，每次询问就给你两个数字 X,Y要求你说出 X 到 Y 这段区间内的最大数。 输入格式 第一行两个整数 N,M 表示数字的个数和要询问的次数； 接下来一行为 N 个数； 接下来 M 行，每行都有两个整数 X,Y。 输出格式 输出共 M 行，每行输出一个数。 数据范围 1≤N≤100000， 1≤M≤1000000， 1≤X≤Y≤N， 数列中的数字均不超过2^31-1 输入样例： 10 2 3 2 4 5 6 8 1 2 9 7 1 4 3 8
输出样例： 5 8
分析：
这个题目和 线段树区间查询、元素修改 基本方法差不多，都是线段树 只需要把节点的 区间和 属性改成 区间最大值 即可 struct node{ int l,r,maxx;//区间最大值 }nodes[N*4];
具体实现：
#include
#include
#include
#include
#include //使用INT_MIN需要添加这个库函数
//这里找出的最大值可能有负数
using namespace std;
const int N = 1e5+10;
int a[N];
int n,m;
struct node{
int l,r,maxx;
}nodes[N*4];
void pushup(int u){
nodes[u].maxx = max(nodes[u 1;
build(u > m;
for (int i = 1; i 0;i -= lowbit(i)){
res += a[i];
}
return res;
}
int main()
{
cin >> n;
for(int i = 1;i > a >> b;
add(a+1,1); //跳过0，因为这个树状数组以0为结束终点
cnt[query(a+1)]++; //前面有多少个星星，就是多少级
}
for (int i = 1; i 0;j -= lowbit(j)){
res += a[j];
}
}
return res;
}
但是这样的操作显然效率过低——计算了大量的重复差分 所以需要改进 a[1] a[1]+a[2] ... ... a[1]+a[2]+..+a[n-1] a[1]+a[2]+...... + a[n]//转化成一个正方体 a[1]+a[2]+...... + a[n] a[1]+a[2]+...... + a[n] ... ...（总共n+1行，在最上面添加一行） a[1]+a[2]+...... + a[n] a[1]+a[2]+...... + a[n] 计算公式=> (n+1)(a[1]+a[2]+......+a[n]) - (1*a[1]+2*a[2]+......+n*a[n])
所以我们可以维护两个树状数组 a[ i ] b[ i ] = i * a[ i ] 代码实现 #include #include #include using namespace std; typedef long long LL; const LL N = 1e5+10; LL a[N],b[N]; LL n,m; LL lowbit(LL x) // 返回末尾的1 { return x & -x; } void add(LL x,LL w){ for(LL i = x;i 0;i -= lowbit(i)){ //优化的区间查询方案 res += (u+1) * a[i] - b[i]; //计算公式 } return res; } //-----------------------------------------------//朴素代码，对于此题超时 /* void add(LL x,LL w){ for(LL i = x;i 0;i--){ for(LL j = i;j > 0;j -= lowbit(j)){ res += a[j]; } } return res; } *///------------------------------------------------ int main() { cin >> n >> m; LL t1=0,t2=0; for (LL i = 1; i > t2; add(i,t2-t1); t1=t2; } for(LL i = 1;i > x; if(x == 'Q'){ LL a,b;cin >> a >> b; cout a >> b >> c; add(a, c); add(b+1, -c); } } return 0; }
〔manim | 算法 | 数据结构〕 完全理解并深入应用树状数组 | 支持多种动态维护区间操作_哔哩哔哩_bilibili 树状数组 数据结构详解与模板(可能是最详细的了)_bestsort的博客-CSDN博客_树状数组 最后贴一下 Code（分块）O(m√n) #include #include #include #include using namespace std; typedef long long LL; const int N = 1e5 + 10, M = 350; int n, m, len; LL sum[M], flag[M]; //sum：块的总和；flag：块的懒标记 int w[N]; int get(int i) { return i / len; } void modify(int l, int r, int d) { if (get(l) == get(r)) //段内直接暴力 { for (int i = l; i |
【本文地址】