前缀和、树状数组和线段树

1.前缀和
前缀和说直白点其实就是先计算出某一个区间内元素的和保存在一个数组中，以便于后续的快速查找某区域内元素的和，细分为一维前缀和和二维前缀和。

一维前缀和
有数组A，数组A对应的前缀和数组为S，有：
$图片说明$
由此方便了范围查询：
$图片说明$
二维前缀和
对于二维数组A，数组A对应的前缀和数组为S，有：
$图片说明$
计算时二维前缀和时，可以使用递推公式：
$图片说明$
当求被点(x1,y1)和点(x2,y2)围起来的元素的和时，可以使用：
$图片说明$

差分
差分可解决范围更新的问题。
思想：延后更新、更新的起点和终点、利用前缀和

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
int a[maxn],b[maxn];
int main(){
  int i,j,k,n,m,p;
  cin>>n>>m;
  for(i=1;i<=n;i++){
      cin>>a[i]; // 原始数组
  }
  for(i=1;i<=m;i++){ // 使用另外一个数组来记录累加和
      int L,R,t;
      cin>>t>>L>>R>>p;
      if(t==1){
          b[L]+=p;b[R+1]-=p;
      }
      else{
          b[L]-=p;b[R+1]+=p;
      }
  }
  int add=0;
  for(i=1;i<=n;i++){
      add+=b[i]; // 累加和
      a[i]+=a[i-1]+add; // 前缀和
  }
  int x,y;
  cin>>x>>y;
  cout<<a[y]-a[x-1]<<endl;
}

2.树状数组
树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于数组的单点修改和区间求和。主要根据二进制特征进行update和getSum。
树状数组的形状
图片说明
需要注意的是，图中的子节点包括自己，比如说8这个节点，里面的值是原始数组中[5,8]的和，标记为灰色的节点实际已被上层覆盖,不占据空间。编号为x的结点上统计着[x−lowbit(x)+1,x]这一段区间的信息，x的父亲就是x+lowbit(x)。
下面是二进制版本，能看到：
图片说明
更新过程是每次加了个二进制的低位1(101+1 ->110, 110 + 10 -> 1000, 1000 + 1000 -> 10000)
查询过程每次就是去掉了二进制中的低位1(1111 - 1 -> 1110, 1110 - 10 -> 1100, 1100 - 100 -> 1000)
int lowbit(x){return x&(-x);}函数可以实现取最低位的1.
单点更新:
继续看开始给出的图，假如此时如果要更改A[1]，则有以下需要进行同步更新
1(0001) C[1]+=A[1]
lowbit(1)=0001 1+lowbit(1)=2(0010) C[2]+=A[1]
lowbit(2)=0010 2+lowbit(2)=4(0100) C[4]+=A[1]
lowbit(4)=0100 4+lowbit(4)=8(1000) C[8]+=A[1]
lowbit(8)=1000 8+lowbit(8)=16(10000) C[16]+=A[1]
换成代码就是:

void update(int x,int y,int n){
    for(int i=x;i<=n;i+=lowbit(i))    //x为更新的位置,y为更新后的数,n为数组最大值
        c[i] += y;
}

区间查询:
举个例子 i=5
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
可以推出: sum(i = 5) ==> C[4]+C[5];
序号写为二进制: sum(101)=C[(100)]+C[(101)];
第一次101,减去最低位的1就是100;
其实也就是单点更新的逆操作，代码如下：

int getsum(int x){
    int ans = 0;
    for(int i=x;i;i-=lowbit(i))
        ans += c[i];
    return ans;
}

下面就给出一些例题强化一下概念。
例题1.leetcode 307. 区域和检索 - 数组可修改
给你一个数组 nums ，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。
典型的使用前缀和或者树状数组的使用，这里我们使用树状数组来求解，代码如下：
class NumArray {
private:
int n;
vector<int> tree;
vector<int> Nums;
public:
// 树状数组
int lowbit(int x)
{
return x & (-x);
}
// 初始化给每个节点加入树状数组中
NumArray(vector<int>& nums) {
n = nums.size();
Nums = nums;
tree = vector<int>(n + 1, 0);
for(int i = 1; i <= n; i++)
add(i, Nums[i - 1]);
}</int></int></int></int>

void add(int index, int val)
{
    while(index <= n)
    {
        tree[index] += val;
        index += lowbit(index);
    }
}
// 记住 这里更新的是差值
void update(int index, int val) {
    int delta = val - Nums[index];
    Nums[index] = val; 
    add(index + 1, delta);
}

int query(int index)
{
    int sum = 0;
    while(index > 0)
    {
        sum += tree[index];
        index -= lowbit(index);
    }
    return sum;
}
// 这里区间和是闭区间
int sumRange(int left, int right) {
    return query(right + 1) - query(left);
}

};
例题2 HDU1166 敌兵布阵
#include <iostream>
using namespace std;
int lowbit(int x){
return x & (-x);
}
const int maxn = 51e4+5;
const int INF = 0x3f3f3f3f;
int c[maxn];
void update(int x,int y,int n){ // 更新操作
for(int i=x;i<=n;i+=lowbit(i))
c[i] += y;
}
int getsum(int x){
int ans = 0;
for(int i=x;i;i-=lowbit(i))
ans += c[i];
return ans;
}
int main()
{
int t;
int n;
int x,y,z;
string s;
cin >> t ;
for(int j=1;j<=t;j++){
cin>>n;
memset(a,0,(n+1)<<2); //初始化数组中前n+1个数为0
for(int i=1;i<=n;i++){
cin>>a;
update(i,z,n);
}
cout <<"Case "<<j<<":"<<endl;
while(1){
cin >> s;
if(s[0] == 'E')
break;
cin>>x>>y;
if(s[0] == 'Q')
cout << getsum(y)-getsum(x-1)<<endl;
else if(s[0] == 'A')
update(x,y,n);
else
update(x,-y,n);
}
}
return 0;
}
上面的树状数组主要展示的是进行单点更新和区间求和，下面再介绍一下另外两种，分别是区间更新和单点求和、区间更新和区间求和。
先来看看区间更新和单点求和，假如更新的区间是[l,r]，那么这个要利用差分的思想就行了，每次在数组的l处加v，r+1处减v，然后一个数的值就是[1,x]的差分和，也就是要选择引入delta数组（差分数组），查询的时候求delta数组的前缀和，再加上原始的a数组就可以了。
再来看看区间更新和区间求和，首先依旧是引入delta数组（差分数组）， delta[i]表示区间 [i, n] 的共同增量，于是修改区间 [l, r] 时修改 delta[l] 和 delta[r + 1] 即可（就是差分的思路），查询的时候是查询区间 [l, r] 的和即sum[r] - sum[l - 1] 所以现在的问题是求sum[i]，
sum[i] = a[1]+...+a[i] + delta[1]*i + delta[2](i - 1) + delta[3](i - 2)+...+delta[i]1 // a[i]为原始数组
= sigma( a[x] ) + sigma( delta[x] * (i + 1 - x) )
= sigma( a[x] ) + (i + 1) * sigma( delta[x] ) - sigma( delta[x] * x )
其中 sigma( a[x] ) 是可以预处理出来的于是只需要维护 delta[x] 与 delta[x] * x 的前缀和（作为两个树状数组就可以了）。
下面看一道例题， codevs1082 线段树练习3 </iostream>

#include <cstdio>
#include <iostream>
using namespace std;
int lowbit(int x)
{
    return x & -x;
}
int readint()
{
    int sign = 1, n = 0; char c = getchar();
    while(c < '0' || c > '9'){ if(c == '-') sign = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { n = n*10 + c-'0'; c = getchar(); }
    return sign*n;
}

const int Nmax = 200100;

int N, Q;

long long delta[Nmax]; // delta的前缀和 
long long deltai[Nmax]; // delta * i的前缀和 
long long sum[Nmax]; // 原始前缀和

long long Query(long long *array, int pos)
{
    long long temp = 0ll;
    while(pos > 0)
    {
        temp += array[pos];
        pos -= lowbit(pos);
    }
    return temp;
}

void Update(long long *array, int pos, int x)
{
    while(pos <= N)
    {
        array[pos] += x;
        pos += lowbit(pos);
    }
}

int main()
{
    N = readint();
    for(int i = 1; i <= N; ++i)
    {
        int x = readint();
        sum[i] = sum[i - 1] + x;
    }

    Q = readint();
    while(Q--)
    {
        int sign = readint();
        if(sign == 1) // 修改：把[l, r]区间均加上x 
        {
            int l = readint(), r = readint(), x = readint();
            Update(delta, l, x); // 更新，使用差分
            Update(delta, r+1, -x);
            Update(deltai, l, x * l); // 更新，使用差分
            Update(deltai, r+1, -x * (r+1));
        } 
        else // 查询：[l, r]区间和 
        {
            int l = readint(), r = readint(); 
            long long suml = sum[l - 1] + l * Query(delta, l - 1) - Query(deltai, l - 1);
            long long sumr = sum[r] + (r + 1) * Query(delta, r) - Query(deltai, r);
            printf("%lld\n", sumr - suml);
        }
    }

    return 0;
}

线段树
1、线段树的每个节点都代表一个区间；
2、线段树具有唯一的根节点，代表的区间是整个统计范围；
3、线段树的每个叶节点都代表一个长度为1的元区间[x,x]；
4、对于每个内部节点[l,r]，它的左子节点是[l,mid]，右子节点是[mid+1,r]，其中mid=(l+r)/2;
图片说明
因为线段树是一颗二叉树，所以我们可以用p∗2来记录p的左儿子，p∗2+1记录右儿子。这样子的话，因为最后一层可能前面全部空出来，单出一个区间[n,n]在这一层的最后面，所以空间要开到4∗n才不会段错误。
线段树节点定义如下：

struct node{
    int l,r,dat; // 左孩子节点、右孩子节点和节点值
};

建树操作如下：

void build (int p,int l,int r) {
    t[p].l=l,t[p].r=r;    //节点p代表区间[l,r];
    if (l==r){
        t[p].dat=a[l];
        return;              //叶节点; 
    } 
    int mid=(l+r)/2;      //折半(根据“父子二倍”,求mid;
    build(p*2,l,mid);      //构造左子节点，即[l,mid],编号p*2;
    build(p*2+1,mid+1,r); //同上一步，构造右子节点，即[mid+1,r],编号p*2+1;
    t[p].dat=max(t[p*2].dat,t[p*2+1].dat); // 选择区间最大值
    //从下往上传递信息; 
}
build (1,1,n); //调用入口;

单点修改,所谓单点修改就是以下步骤：
1.从根节点出发，递归找到代表区间[x,x]的叶节点；
2.更新（从下往上）[x,x]以及其所有祖先节点上的信息；
3.时间复杂度为O(logN);
代码如下：

void modify(int p,int x,int v) {
    if (t[p].l==t[p].r) {
        t[p].dat=v;
        return;            //找叶节点; 
    }
    int mid=(t[p].l+t[p].r)/2;    //折半; 

    if (x<=mid)            //找x所属的区间
        change(p*2,x,v); 
    else
        change(p*2+1,x,v); 
    t[p].dat=max(t[p*2].dat,t[p*2+1],dat); 
} 

modify(1,x,v); //调用入口;

区间查询
递归：
1.[l,r]完全覆盖了当前节点代表的区间，回溯，该节点的dat值为候选答案；
2.左子节点与[l,r]有重叠部分，递归访问左子节点；
3.右子节点与[l,r]有重叠部分，递归访问右子节点；

int query(int p,int l,int r) {
    if (l<=t[p].l &&r>=t[p].r)    return t[p].dat; //完全包含; 
    int mid=(t[p].l+t[p].r)/2; 
    int val=a(1<<30);
    if (l<=mid) val=max(val,ask(p*2,l,r)); //与左子节点有重叠;
    if (r>mid)    val=max(val,ask(p*2+1,l,r)); //与右子节点有重叠;
    return val; 
}
cout<<query(1,l,r)<<endl; //调用入口;

一些简单例题如 https://www.acwing.com/problem/content/1266/ https://www.acwing.com/problem/content/1272/
参考连接：
https://blog.csdn.net/aga28832/article/details/102271743?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_title-8&spm=1001.2101.3001.4242
https://blog.csdn.net/weixin_46704467/article/details/110260672