树状数组算法

树状数组是什么

树状数组是一种数据结构，提供O(logn)时间内的单点修改和区间求和操作，比线段树有更优的常数因子。它利用二进制特性进行快速更新和查询，常见于数组操作问题。文章通过代码示例解释了树状数组的核心操作和单点修改、区间查询的实现原理。

树状数组与线段树的区别与联系

1.两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树.

2.树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决.

3.树状数组的突出特点是其编程的极端简洁性, 使用lowbit技术可以在很短的几步操作中完成树状数组的核心操作，其代码效率远高于线段树。

树状数组讲解

学树状数组之前要先知道lowbit函数
lowbit这个函数的功能就是求某一个数的二进制表示中最低的一位1，举个例子，x = 6，它的二进制为110，那么lowbit(x)就返回2，因为最后一位1表示2
lowbit函数要自己写 c++库里面没有 代码如下

int lowbit（int n）
{return n&-n;
}

看下图我们会发现，数组的下标其实是有规律的，就比如下标为1，3，5，7的二进制最后一位1都是2⁰ 为第0层 ,下标为2，6的二进制最后一位1都是2¹ 为第1层，下标为4的二进制最后一位1都是2² 为第2层，下标为8的二进制最后一位1都是2³ 为第3层，这样我们就可以找到一定的规律构造s数组

s数组对本身数组区间求和有很大的帮助，下图change函数就是构建s数组的过程，query函数就是求前缀和的函数

点修，区查，讲解及模板

点修和区查的意思就如下图所示

就比如他给你一个数组个数为n
在输入数组时，咱们也把s数组构建好
然后她再给你一个下标x，和一个数y让你执行操做1，就可以执行这样的操作 change(x,y) 就可以了
如果给你两个下标让你求区间和就可以执行query(y)-query(x)
例题链接
代码如下

#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define int long long
#define endl '\n'
#define PII pair<int,int> 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int a[500100],m,n; 
void asd(int x,int y)
{while(x<=n){a[x]+=y;x+=lowbit(x); }
}
int sum(int x)
{int t=0;while(x){t+=a[x];x-=lowbit(x); }return t;
}
signed main()
{IOSint c;cin>>n>>m;for(int i=1;i<=n;i++){cin>>c;asd(i,c);}while(m--){int b,x,y;cin>>b>>x>>y;if(b==1)asd(x,y);elsecout<<sum(y)-sum(x-1)<<endl; }return 0;
}

点查，区修讲解及模板

点查和区修的意思如下

首先想学会这个需要先知道差分
不知道差分的点这里
看完下边就理解了
在输入数组时，咱们也把差分的s数组构建好
如果给你两个下标让你执行操作2就可以这样操作change(l,x) change(r,-x)
然后她再给你一个下标x，让你执行操做2，就可以执行这样的操作query(x)
例题链接
代码如下

#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define int long long
#define endl '\n'
#define PII pair<int,int> 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int m,n,a[500100];
void asd(int x,int y)
{while(x<=n){a[x]+=y;x+=lowbit(x);}
}
int sum(int x)
{int t=0;while(x){t+=a[x];x-=lowbit(x);}return t;
}
signed main()
{IOSint c=0,d;cin>>m>>n;for(int i=1;i<=m;i++){cin>>d;asd(i,d-c);c=d; }for(int i=1;i<=n;i++){int b,x,y,t;cin>>b;if(b==1){cin>>x>>y>>t;asd(x,t);asd(y+1,-t);}else{cin>>x;cout<<sum(x)<<endl;}}return 0;
}