前言

树状数组比线段树好写很多，虽然功能少点，但是有的时候已经可以满足一般题目的要求。

推荐一篇博客：https://bestsort.cn/2019/04/26/195/

我就是看着这个学的。

正文

第一节

这一节要实现的是单点修改和区间查询。

核心就是lowbit

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

单点修改和区间查询都是基于lowbit来实现的。

单点修改代码

void update(int x,int y){//把第x个元素增加y
    for(int i=x;i<=n;i+=lowbit(i))//此处的n是你的元素的数量。
        c[i] += y;
}

区间查询代码

int getsum(int a)
{
    int ans=0;
    for(int i=a;i;i-=lowbit(i))
        ans+=q[i];
    return ans;
}

第二节

这节要实现的是区间修改和单点查询。

树状数组模板题2

#include<bits/stdc++.h>
using namespace std;
int q[500005],w[500005],n,m;
int lowbit(int a){return a&(-a);}
void add(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
        w[i]+=y;
}
void qujian_add(int x,int y,int k){
    add(x,k);add(y+1,-k);
}
int ask(int a)
{
    int res=0;
    for(int i=a;i;i-=lowbit(i))
        res+=w[i];
    return res;
}
int main()
{
    int a,x,y,z;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>q[i];
        add(i,q[i]-q[i-1]);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>a;
        if(a==1)
        {
            cin>>x>>y>>z;
            qujian_add(x,y,z);
        }
        else if(a==2)
        {
            cin>>x;
            cout<<ask(x)<<endl;
        }
    }
}

本蒟蒻文笔不好，请大佬多多包涵