关键步骤

1.建树c[x]:它管辖a[x-lowbit(x)+1,x]这些范围,初始化时一般是单点修改（加a[i]即可），时间复杂度o(nlogn)

2.几个关键函数

（1）返回最后一个1的位置

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

（2）单点修改

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

（3）区间查询

int getsum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}

涉及（4）（5）操作这里树状数组不需要初始化（做题时是这样的，欢迎评论区指正）

（4）区间修改

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

（5）单点查询

int ask(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}

3.实现的操作

（1）树状数组初始化

for(int i=1;i<=n;i++)
    add(i,a[i]);

（2）区间查询和单点修改

getsum(r)-getsum(l-1);
add(x,k);

（3）区间修改和单点查询

add(x,z);add(y+1,-z);

a[x]+ask(x);

例题

洛谷树状数组1

代码：

//树状数组复习
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,c[N],op,a[N];
int lowbit(int x)
{
    return x&-x;
}
int getsum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
void add(int x,int v)
{
    while(x<=n)
    {
        c[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i);

    for(int i=1;i<=n;i++)
    add(i,a[i]);

    while(m--)
{
    scanf("%d",&op);
    if(op==2)
    {
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d\n",getsum(r)-getsum(l-1));
    }
    else 
    {
    int x,k;
    scanf("%d%d",&x,&k);
    add(x,k);   
    }   
}
    return 0;
}

洛谷树状数组2

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,a[N],c[N];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int v)
{
    while(x<=n)
    {
        c[x]+=v;
        x+=lowbit(x);
    }
}
int ask(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    while(m--)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,z);
            add(y+1,-z);
        }
        else 
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",a[x]+ask(x));
        }
    }



    return 0;
}