告知
本博客是由一个蒟蒻编写，内容可能出错，若发现请告诉本蒟蒻，以便大众阅读
线段树和树状数组是兄弟来的
它们之间的关系
树状数组可以解的，线段树能解
树状数组不可以解的，线段树还是可以解
既然这样，那我学会线段树不就搞定了吗，干嘛还学树状数组呀
那么，树状数组优在何处呢？
其实呢，就是吧
对比一下
单点修改区间查询
线段树100行起步
树状数组呢，50行左右吧
区间修改区间查询
线段树估计要飙到150了吧
树状数组依旧50行
没有对比就没有伤害呀
这时，有些线段树忠实粉或许会思考人生：
那么\(x\&(-x)\)是什么意思呢
首先说明\(-x\)在二进制下和\(x\)的关系
在二进制下，\(-x\)就是\(x\)取反后再加1
例如，\(10_{10}=01010_2\)，那么\(-10_{10}=10101_2+1_2=10110_2\)（第一位是符号位）
进行按位与运算后，答案就是\(00010_2=2^1=2_{10}\)（第一位是符号位）
眼睛扫一扫，发现答案就是\(2\)
神奇吧
具体证明呢，我也不会，嘻嘻（毕竟我只是一个蒟蒻）
基本应用
1.单点修改，区间查询
修改
若要更新当前节点的\(a[i]\)
那么是不是可以直接更新\(a[i]\)的上级，\(a[i]\)上级的上级，以此类推
用\(lowbit\)到上级所在下标
void update(int now,int x)
{
int i;
for (i=now;i<=n;i+=lowbit(i))
c[i]+=x;
}
查询
对于区间查询，我们采取前缀和的求法
对于一个区间\([l,r]\)，我们求出\(r\)的前缀和，减去\(l-1\)的前缀和即为答案
查询的具体过程呢，也很简单
就是从要查的节点以此往下，搜索下级
依旧是用\(lowbit\)
int get(int x)
{
int i,ans;
ans=0;
for (i=x;i>=1;i-=lowbit(i))
ans+=c[i];
return ans;
}
题目
Code
#include<cstdio>
#include<iostream>
using namespace std;
long long n,m,i,x,y,ch,c[1000005];
long long lowbit(long long x)
{
return x&(-x);
}
void update(long long now,long long x)
{
long long i;
for (i=now;i<=n;i+=lowbit(i))
c[i]+=x;
}
long long get(long long x)
{
long long i,ans;
ans=0;
for (i=x;i>=1;i-=lowbit(i))
ans+=c[i];
return ans;
}
int main()
{
scanf("%lld%lld",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%lld",&x);
update(i,x);
}
for (i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&ch,&x,&y);
if (ch==2) printf("%lld\n",get(y)-get(x-1));
else update(x,y);
}
return 0;
}
2.区间修改，单点查询
修改
引入差分的思想，记录数组里每个元素与前一个元素的差，那么\(a_i=\sum_{j=1}^i d_j\)，如果修改区间\([l,r]\)，令其加上\(x\)，那么\(l\)与\(l-1\)的差增加了\(x\)，\(r\)与\(r+1\)的差减小了\(x\)，根据差分，就可以给\(d_{l}\)加上\(x\)，给\(d_{r+1}\)减去\(x\)
查询
直接根据\(a_i=\sum_{j=1}^i d_j\)，查前缀和就好
题目
Code
#include<cstdio>
using namespace std;
int n,m,i,l,r,x,bj;
long long a[1000005],c[1000005];
int lowbit(int x)
{
return x&(-x);
}
void update(int now,int x)
{
int i;
for (i=now;i<=n;i+=lowbit(i))
c[i]+=x;
}
long long get(int x)
{
int i;
long long ans;
ans=0;
for (i=x;i;i-=lowbit(i))
ans+=c[i];
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
update(i,a[i]-a[i-1]);
}
for (i=1;i<=m;i++)
{
scanf("%d",&bj);
if (bj==1)
{
scanf("%d%d%d",&l,&r,&x);
update(l,x);
update(r+1,-x);
}
else
{
scanf("%d",&x);
printf("%lld\n",get(x));
}
}
return 0;
}
3.区间修改，区间查询
这个也是线段树最麻烦的地方，通常100行起步，但树状数组就不用了，实测50行不到，而且我不压行
先看一下如果按照问题2的方法来求区间前缀和，要怎么求
位置\(x\)的前缀和=\(\sum_{i=1}^x\sum_{j=1}^id_j\)，发现在这个式子里，\(d_1\)被计算了\(x\)此，\(d_2\)被计算了\(x-1\)次……，\(d_x\)被计算了1次。那么这个式子就可以转化为
\(\sum_{i=1}^xd_i\times(x-i+1)=(x+1)\sum_{i=1}^xd_i-\sum_{i=1}^xd_i\times i\)
其中\(x+1\)是给出的，那么我们记录\(d_i\)和\(d_i\times i\)就可以了
维护两个数组\(sum1\)和\(sum2\)，分别记录\(d_i\)和\(d_i\times i\)
修改
\(sum1\)同问题2的\(d\)，\(sum2\)也类似，\(l\)加上\(l\times x\)，\(r+1\)减去\((r+1)x\)
查询
单点\(x\)的前缀和就是\((x+1)\times sum1\)中\(x\)的前缀和-\(sum2\)中\(x\)的前缀和，区间\([l,r]\)的值就是\(r\)的前缀和-\(l-1\)的前缀和
题目
Code
#include<cstdio>
using namespace std;
long long n,m,i,l,r,x,bj,a[1000005],c1[1000005],c2[1000005];
long long lowbit(long long x)
{
return x&(-x);
}
void update(long long k,long long x)
{
long long i;
for (i=k;i<=n;i+=lowbit(i))
{
c1[i]+=x;
c2[i]+=x*k;
}
}
long long get(long long x)
{
long long i,ans;
ans=0;
for (i=x;i;i-=lowbit(i))
ans+=((x+1)*c1[i])-c2[i];
return ans;
}
int main()
{
scanf("%lld%lld",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
update(i,a[i]-a[i-1]);
}
for (i=1;i<=m;i++)
{
scanf("%lld",&bj);
if (bj==1)
{
scanf("%lld%lld%lld",&l,&r,&x);
update(l,x);
update(r+1,-x);
}
else
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",get(r)-get(l-1));
}
}
return 0;
}
小结
线段树与树状数组有很多相似的地方，但是树状数组很明显的优势就是短，但是线段树可以处理很多种情况，而这里面有些是树状数组做不到的，所以说不论是线段树还是树状数组，我们都应该学习一下，然后选择更好的去解决题目。
不定时更新高阶操作