# 树状数组模板

# 一、树状数组大致介绍

1、树状数组就是模拟树形结构的一个数组

2、树状数组解决的问题大部分是区间上的更新以及求和

3、树状数组的修改和查询的复杂度都是$O(logn)$

4、树状数组的大致形状如下图：

具体原理请移步另一篇文章，本篇只搬运模板

# 二、例题和模板

例题：树状数组

Code:

#include <cstdio>
#include <cstdlib>
using namespace std;
int n;
const int N=500001;
int d[N];
int m;
int cf[N];
int lowbit(int x)
{
    return x & -x;
}
int add(int wz,int v)
{
    while(wz<=n)
    {
        cf[wz]+=v;
        wz+=lowbit(wz);
    }
}
int get_ans(int x)
{
    int cnt=0;
    while(x>0)
    {
        cnt+=cf[x];
        x-=lowbit(x);
    }
    return cnt;
}
int main()
{
    scanf("%d %d",&n,&m);
    int c;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c);
        add(i,c);
        add(i+1,-c);
    }
    for(int i=0;i<m;i++)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int l,r,z;
            scanf(" %d %d %d",&l,&r,&z);
            add(l,z);
            add(r+1,-z);
        }
        else
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",get_ans(x));
        }
    }
    return 0;
}