• 前缀和
  • 一维数组前缀和
  • 二维数组前缀和
• 差分
• 二叉堆

前缀和

一维数组前缀和

代码如下：

for(int i=0;i<n;i++){
  if(i==0) y[i]=x[i];
  else y[i]=y[i-1]+x[i];
}

或者

for(int i=1;i<=n;i++){
    y[i]=y[i-1]+x[i];
}

二维数组前缀和

代码如下：

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
         cin>>a[i][j];
         b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];  
    }
}

差分

差分就是前缀和的逆运算

b[i]=a[i]-a[i-1];

还原差分

a[i]=a[i-1]+b[i];

二叉堆

1. 上浮

void swim(int n)
{
	for(int i = n;i > 1 && heap[i] > heap[i/2]; i /= 2){
		swap(heap[i],heap[i / 2]);
	}
}

2. 下沉

void sink(int n)
{
	for(int i = n,t = son(i);t <= size && heap[t] > heap[i] i = t,t = son(i)){
		swap(heap[i],heap[t]);
	}
}

3. 插入

  void insert(int x)
{
	heap[++size] = x;
	swim(size);
}

4. 找到需要交换的那个子节点

int son(int n)
{
	return n * 2 + (n * 2 + 1 <= size && heap[n * 2 + 1] > heap[n * 2]);
}

5. 删除

void pop()
{
	swap(heap[1],heap[size--]);
	sink(1);
}

6. 查询

int top()
{
	return heap[1];
}