树状数组是一种十分优秀的数据结构，拥有常数非常小的特点，好写好调，在一些应用上比线段树要优秀许多。下面我来介绍下树状数组（基础知识请看蓝书或其他神犇的blog，蒟蒻在这里就不多提了）。

区间修改&&区间查询

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数数加上x

2.求出某一个数的和

这里要引入差分数组这种东西，我们记d[i] = a[i] - a[i-1]（a为原数组），这样我们记sigma（d[i]） = a[i] ，为什么呢，观察式子sigma(d[i]) = a[1] + a[2] - a[1] +ａ［３］．．．这样一直下去就得到了我们的原数组。

有什么用呢？如果我们往一段区间上加ｋ，在差分数组上如何体现呢？我们举个栗子：

ａ：１,２,３,４,５

ｄ：１,１,１,１,１

２～４加１

如果我们盲目的在２到４上加１，就会发现会影响后面的数（因为是前缀和），所以我们在２这个位置加一，用树状数组更新，在５的位置减一用树状数组更新就ｏｋ了

ａ：１，３，４，５，５

ｄ：１，２，１，１，０

这样就没问题了吧？总的时间是操作数×ｌｏｇ（ｎ）。

/*************************************************************************    > Author: Drinkwater-cnyali    > Created Time: 2017/6/13 10:22:21 ************************************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)#define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)char buff[1<<25], *buf = buff;#define mem(a, b) memset((a), b, sizeof(a))template
           
             inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }template
            
              inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }int Fread(){ int sum = 0, fg = 1; for(; !isdigit(*buf) ; ++buf)if(*buf == '-')fg = -1; for(; isdigit(*buf); ++buf)sum = sum * 10 + *buf - '0'; return sum * fg;}int read(){ int sum = 0,fg = 1;char c = getchar(); while(c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); } while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); } return sum * fg;}const int maxn = 1000000;const int inf = 0x3f3f3f3f;int n,m;int c[maxn],a[maxn];inline int lowbit(int x) { return (x & (-x));}inline void updata(int x,int num){ for(; x <= n; x += lowbit(x)) c[x] += num;}inline int query(int x){ int ans = 0; for( ; x > 0; x -= lowbit(x)) ans += c[x]; return ans;} int main(){ fread(buff,1,1<<25,stdin); n = Fread(), m = Fread(); REP(i,1,n)a[i] = Fread(), updata(i,a[i] - a[i-1]); REP(i,1,m) { int t = Fread(); if(t == 1) { int x = Fread(), y = Fread(),k = Fread(); updata(x,k),updata(y+1,-k); } if(t == 2) { int x = Fread(); printf("%d\n",query(x)); } } return 0;}
            
           
          
         
        
       
      
     

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.求出某区间每一个数的和

这道题显然是线段树区间更新的裸题，这里我们要对式子进行变形

一个区间和我们记为sigma（ａ[i]） = d[1] + (d[1] + d[2]) + (d[1] + d[2]+ d[3]) + ..+(…d[n])

= nd[1] - (n-1)d[2] + ..+d[n]

= n * (d[1] + ..+d[n]) - (0d[1] + 1d[2] + ..+(n-1)d[n])

这样我们就只需要维护一个d的前缀和和(i-1)*d[i]的前缀和就好了。

/*************************************************************************    > Author: Drinkwater-cnyali    > Created Time: 2017/6/13 15:36:58 ************************************************************************/#prag\ma GCC optimize("O4")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)#define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)char buff[1<<25], *buf = buff;#define mem(a, b) memset((a), b, sizeof(a))template
           
             inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }template
            
              inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }LL Fread(){ LL sum = 0, fg = 1; for(; !isdigit(*buf) ; ++buf)if(*buf == '-')fg = -1; for(; isdigit(*buf); ++buf)sum = sum * 10 + *buf - '0'; return sum * fg;}int read(){ int sum = 0,fg = 1;char c = getchar(); while(c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); } while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); } return sum * fg;}const int maxn = 100000+10;const int inf = 0x3f3f3f3f;LL n,m;LL a[maxn],c1[maxn],c2[maxn];int lowbit(int x) { return (x & (-x));}void updata(int x,int num,int t){ if(t == 1) for( ; x <= n; x += lowbit(x)) c1[x] += num; else for(; x <= n; x += lowbit(x)) c2[x] += num;} LL query(int x,int t){ LL ans = 0; if(t == 1) for(; x > 0; x -= lowbit(x)) ans += c1[x]; else for(; x > 0; x -= lowbit(x)) ans += c2[x]; return ans;}int main(){ fread(buff,1,1<<25,stdin); n = Fread(), m = Fread(); REP(i,1,n) a[i] = Fread(), updata(i,a[i]-a[i-1],1),updata(i,(a[i]-a[i-1])*(i-1),2); REP(i,1,m) { LL t = Fread(); if(t == 1) { LL x = Fread(), y = Fread(), k = Fread(); updata(x,k,1),updata(y + 1, -k, 1); updata(x, (x-1) * k, 2), updata(y+1, -y * k, 2); } if(t == 2) { LL x = Fread(), y = Fread(); LL sum1 = query(x-1,1) * (x-1) - query(x-1,2); LL sum2 = query(y,1) * y - query(y,2); printf("%lld\n",sum2 - sum1); } } return 0;}
            
           
          
         
        
       
      
     

逆序对

这里我们以权值为下标构建树状数组统计比当前点大的数的个数，边读边更新。

/*************************************************************************    > Author: Drinkwater-cnyali    > Created Time: 2017/5/25 10:51:38 ************************************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)#define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)#define debug(...) fprintf(stderr, __VA_ARGS__)#define mem(a, b) memset((a), b, sizeof(a))template
           
             inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }template
            
              inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }int read(){ int sum = 0, fg = 1; char c = getchar(); while(c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); } while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); } return sum * fg;}const int maxn = 100000;const int mod = 99999997;typedef pair
             
               P;P a[maxn],b[maxn];int n;int c[maxn],t[maxn];bool cmp(P u,P v){ return u.first < v.first;}int lowbit(int x){ return (x & (-x));}void updata(int x){ while(x <= n) t[x]++,x += lowbit(x);}int get_sum(int x){ int ans = 0; while(x > 0) { ans += t[x]; x -= lowbit(x); } return ans;}int main(){ n = read(); REP(i,1,n)a[i].first = read(),a[i].second = i; REP(i,1,n)b[i].first = read(),b[i].second = i; sort(a+1,a+1+n,cmp);sort(b+1,b+1+n,cmp); REP(i,1,n)c[a[i].second] = b[i].second; int ans = 0; for(int i = n; i >= 1; --i) { ans = (ans%mod + get_sum(c[i])%mod)%mod; updata(c[i]); } cout<
              
               <