一、树状数组

1.简介

支持区间查询、区间修改，树状数组实现

2.使用方法

声明 ：binary_tree 对象名称
node ：树状数组的数据类型
maxN ：数据范围
c(初始化数组,元素个数,操作对象) ：初始化操作，为元素赋初值
u(操作对象,left,right,value) ：将 \([left,right]\) 内的元素都增加 \(value\)
q(操作对象,left,right) ：求 \([left,right]\) 区间内的元素和

3.代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define node long long
#define fm(x) memset(x,0,sizeof(x))
#define u(p,x,y,w) p.modify(x,w),p.modify(y+1,-w)
#define q(p,x,y) p.query(y)-p.query(x-1)
#define c(f,x,p) p.clear(f,x)
#define maxN 100000

class binary_tree
{
    public:
        void clear(node a[],node n)
        {
            tot=n; fm(tree1); fm(tree2);
            for(register int i=1;i<=tot;i++) modify(i,a[i]-a[i-1]);
        }
        void modify(node x,node val) {update(tree1,x,val); update(tree2,x,val*x);}
        node query(node x) {return (x+1)*sum(tree1,x)-sum(tree2,x);}
    private:
        node tree1[maxN+1],tree2[maxN+1],tot;
        inline node lowbit(node x) {return x&(-x);}
        node sum(node a[],node x) {node an=0; while(x>0) {ans+=a[x]; x-=lowbit(x);} return an;}
        void update(node a[],node x,node val) {while(x<=tot) {a[x]+=val; x+=lowbit(x);}}
};