树状数组

luckydrawbox · 2021-10-11 15:26:18 · 个人记录

你可以通过 TA\_T 更改树状数组维护的基本类型。

#define TA_T int

上面的基础类型是 \text{int}。

变量

• n：树状数组的元素个数。
• a[i]：元素 a_i。

底层操作

• lowbit(x)：得到 x 二进制下最后一个 1 所表示的数，常用于树状数组父亲与儿子的转化。
• clear(p)：清空树状数组，把所有值改成 p。
• op(x,y)：代表维护树状数组所用的运算，如加和等，可根据情况自己设定。

普通操作

• init(m,b)：将树状数组初始化为 b 数组的 b_{1\sim m}，元素个数为 m。
• change(x,val）：把第 x 个元素用 val 通过 op(x,y) 修改。
• ask(x)：求 a_{1\sim x} 的元素维护的总值。

#define TA_T int
struct Tree_Array{
    int n;
    TA_T a[N];
    int lowbit(int x){
        return x&-x;
    }
    void clear(TA_T p){
        n=0;
        memset(a,p,sizeof(a));
    }
    TA_T op(TA_T x,TA_T y){
        return x+y;
    }
    void init(int m,TA_T *b){
        n=m;
        for(int i=n;i;i--){
            a[i]=b[i];
            if(i+lowbit(i)<=n)
                a[i+lowbit(i)]=op(a[i+lowbit(i)],a[i]);
        }
    }
    void change(int x,TA_T val){
        for(;x<=n;x+=lowbit(x))
            a[x]=op(a[x],val);
    }
    TA_T ask(int x){
        TA_T ans=p;
        while(x){
            ans=op(ans,c[x]);
            x-=lowbit(x);
        }
        return ans;
    }