Color the ball

一维差分

#include<iostream>
#include<string.h>
using namespace std;
const int N = 100010;
int a[N],D[N];                  //a是气球，D是差分数组
int main(){
  int n;
  while(~scanf("%d",&n)) {      //输入数组长度
  //if (n == 0) break;          //按照原题要求当N=0时结束
    memset(a,0,sizeof(a)); memset(D,0,sizeof(D));    //初始化数组：将0复制到两个数组里
    for(int i=1;i<=n;i++){
      int L,R; scanf("%d%d",&L,&R);
      D[L]++; D[R+1]--;         //区间修改
    }
    for(int i=1;i<=n;i++){      //将L和R的区间修改数值遍历放进数组里
    a[i] = a[i-1] + D[i];       //差分。求前缀和a[]，a[i]就是气球i的值
    if(i!=n) printf("%d ", a[i]);                    //逐个打印结果
    else printf("%d\n",a[i]);
    }                           //小技巧：14行到17行，把a[]改成D[]也行
  }
  return 0;
}

笔记：在频繁修改数组的区间数值，如果遍历的时间复杂度是O(n)，用差分就只需要修改区间的L和R就可以，时间复杂度变成了0(m+n)，提高了修改的效率

区间修改 + 单点查询

#include <iostream>
#include<string.h>
using namespace std;
const int N = 100010;
#define lowbit(x) ((x) & - (x))
int tree[N]={0};
void update(int x, int d) {           //单点修改：修改元素a[x], a[x] = a[x] + d
  while(x <= N) {
    tree[x] += d;
    x += lowbit(x);
  }
}
int sum(int x) {                      //查询前缀和：返回前缀和sum = a[1] + a[2] +... + a[x]
  int ans = 0;
  while(x > 0){
    ans += tree[x];
    x -= lowbit(x);
  }
  return ans;
}
int main(){
  int n;
  while(~scanf("%d",&n)) {
    memset(tree,0,sizeof(tree));      //只需要一个tree[]数组
    for(int i=1;i<=n;i++) {           //区间修改
      int L, R; scanf("%d%d",&L,&R);
      update(L,1);                    //本题的d = 1
      update(R+1,-1);
    }
    for(int i=1;i<=n;i++){            //单点查询
      if(i!=n) printf("%d ",sum(i));  //把sum(i)看成a[i]
      else printf("%d\n",sum(i));
    }
  }
  return 0;
}

笔记：树状数组的作用是“单点修改+区间查询”，配合差分操作，将单点修改变成区间修改。虽然查询从区间查询变成了单点查询，但是也能做到“区间修改 + 区间查询”