高性能问题：
Q：需求：（老板给你分了台2GHz单核，内存500M的服务器然后让你写程序）程序每秒会收到一组数据，每组数据包含10万条命令，总共会有100万个仓库，每个仓库库存没有上限且可为负，库存初始为0。你需要在一秒内完成全部的命令，然后将查询结果按顺序得出后传回，命令如下：

Add i j，i和j为正整数，表示第i个仓库增加j个库存（j不超过220）
Sub i j，i和j为正整数，表示第i个仓库减少个库存（j不超过220）
Query i j，i和j为正整数，i<=j，表示询问第i到第个仓库的总库存；End 表示结束，这条命令在每组数据最后出现；

思路一：用array去存储每个仓库的容量，在查询时用循环取出(L,R)的总容量。此时Update为O(1)，Query为O(N)

思路二：前缀数组和：在array1储存每个仓库容量的同时维护array2来记录前n个仓库的总容量，当计算某个区间的容量(L,R)可以通过s[R]-s[L-1]求出。此时Query为O(1)，但Update为O(N)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3;
int arr[maxn];

int main(){
    int n;
    cin >> n;
    int tmp;
    cin >> tmp;
    arr[1] = tmp;
    for (int i = 2; i <= n; i++) {
       cin >> tmp;
       arr[i] = tmp + arr[i-1];
    }
    for (int i = 1; i <= n; i++) {
       cout << arr[i] <<endl;
    }
    // 可以算出2-4的和
    cout << arr[4] - arr[2-1] << endl;
    return 0;
}

思路三：树状数组：Update和Query的时间复杂度进行折中后都为O(logN)

树状数组

又叫二叉索引树，最早是为了解决数据压缩里的累积频率问题，现多用来解决数组区间查询问题的数据结构，即高效解决数列的前缀和、区间和问题。

low bit算法

核心：将一个数拆分成若干个二进制数相加，原理：每一个数都有二进制表示，即所有数都可以表示成x个不同的2的幂之和。

做法：找到二进制最后低一位1表示的数。
代码：通过计算n&-n找到n最右边的1。

举个栗子：
Q： 6可以怎么计算得到呢？
A： 6==0110，i=110，通过lowbit可以拆分成两个数100+010=110

因此树状数组的维护更新过程如下：已知i=6
①S+= C[6]
②找到i最右边的1，即得到 $lowbit=(10)_{2}=(2)_{10}$
③更新i: $i'= i - lowbit = (0110)_{2}-(0010)_{2}=(0100)_{2}$ ，即 $i'=6-2=(4)_{10}$ ；
④S+= C[4]
⑤再继续找i最右边的1，即得到了 $lowbit=(100)_{2}=(4)_{10}$ ，
⑥更新i: $i'= i - lowbit =(0100)_{2}-(0100)_{2}=(0000)_{2}$ ，
⑦此时i最右边无1(即全零为0)，算法结束，即最终C[6]=C[4] + C[2]

计算步骤：

找到 $(n)_2$ 最右边的1的数 $(n1)_2$
更新 $n'=(n)_2 - (n1)_2$
如果 $(n')_2$ 还能找到1，那么重复1-2

N = 1e6 + 5
arr = [0] * N
# 自底向上建树
def add(i, j):
    '''
    修改第i仓库Ci。但注意执行某个仓库的update操作，后面所有仓库都得更新
    '''
	while i <= N:
        arr[i] += j	 
        # 加上low bit位
        i += i&-i
        
def sub(i, j):
    add(i, -j)
    
def sum(i):
    '''
    通过Ci求出1-i仓库的总库存
    S[6] = C[6] + C[4], 推导如下:
    如果i=6,那么
    ans += c[6] , i <- i-2 = 6-2 = 4,
    ans += c[4] , i <- i-4 = 4-4 = 0
    ∴ans = c[6] + c[4] = A[6]+A[5]+A[4]+A[3]+A[2]+A[1]
    '''
    ans = 0
    while i > 0:
        ans += arr[i]
        i -= i&(-i)
    return ans


def query(i, j);
	'''
	查询某个区间的总库存，sum(i, j) = S(R) - S(L-1)
	'''
	return sum(j) - sum(i-1)

符号说明：

Ai：第i个仓库的库存数
Ci：所构建的数的第i个节点的值，C[i] = A[i-lowbit(i)+1] + …+A[i]
Si：第1个仓库到第i个仓库库存数之和
Ans（i，j）：显然就等于 $S_{R}-S_{L-1}$

形式

一.从原数组A[],维护树状数组C[]

▲lowbit又叫子叶数，表示了有多少个A[]相加，C[i]表示从C[i] = A[i-lowbit(i)+1] + …+A[i] (<===>C[i] = A[i-2^x+1] + … + A[i])，

For Example： i=6

参考：

树状数组——黑板讲解,NICE

树状数组算法——初步了解，有些点讲的并不那么纤细

洛谷: P3374 【模板】树状数组 1

#include <bits/stdc++.h>
#define N 500000 + 5

using namespace std;
int c[N];

void add(int i, int k){
    int index = i;
    while (index<=N){
        c[index] += k;
        index += index&(-index);
    }
}


int sum(int n){
    int index = n;
    int ans = 0;
    while (index){
        ans += c[index];
        index -= index&(-index);
    }
    return ans;
}

int query(int l, int r){
    return sum(r) - sum(l-1);
} 


int main(int argc, char const *argv[]){
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        int val;
        cin >> val;
        add(i, val);
    }
    for (int i = 0; i < m; ++i){
        int op;
        int x, k;
        cin >> op >> x >> k;
        if (op==1) add(x, k);
        else cout << query(x, k) << endl;
    }
    return 0;
}

线段树

在求解前缀和、区间和问题上，两者是没有差别的，并且树状数组的空间复杂度更低。但是线段树还有更多的功能，比如求取区间最大值。

完满二叉树(Full Binary Tree)
根据元素的下标进行划分
一个节点代表一个区间的信息

特点：

每个节点维护一个闭区间1,r的信息。
根节点表示[1,n]的信息。如果1=r那就是叶子结点.
如果1<r那就是内部节点,它有两个子节点[1,(1+r)/2]，[(1+r)/2+1,r].

代码实现

// 更新
/*
用1表示根节点。
下标为x的点的左子节点下标为2x，右子节点2x+1。
用sum[x]表示x代表的区间里所有数的和。
对于叶子结点x，它代表[1，r]（1=r），sum[x]=a[1]
*/
void update(int x){
    // 更新某个节点X的值
	sum[x]= sum[x*2] + sum[x*2+1];
}

// 构建, 自顶向下
/*
对于存储在i号位置的节点，它的左孩子存在2i号位置，右孩子2i+1号位置。
同时我们也不需要记录每个位置对应的区间，只要在递归的找这个点的时候边找边修改即可。
*/
void build(int 1,int r,int x){
    if(l==r){	//叶子结点
        sum[x]=a[1];
        return;
    }
    int mid=(1+r)>〉1;
    build(1,mid,x*2);
    build(mid+1,r,x*2+1);
    update(x);//更新信息
}

// 查询
/*
假设询问区间是[A,B],现在所在的节点表示的区间为[1,r]- 计算mid=(1+r)/2,左子节点的区间为[1,mid],右子节点的区间为[mid+1,r].
如果A<=mid,即询问区间与左子节点有重合,需要递归到左子节点。
如果B>=mid+1,即询问区间与右子节点有重合,需要递归到右子节点。
递归完之后,需要把两个孩子询问的结果加起来作为返回值。
*/
int query(int A,int B,int 1,int r,int x){
    if(A<=1&&r<=B)
    	return sum[x];
    int mid=(1+r)>>1,ans=0;
    if(A<=mid)
    	ans+=query(A,B,1,mid,x*2);
    if(mid<B)
    	ans+=query(A,B,mid+1,r,x*2+1);
    return ans;
}
// 修改
/*
由于修改是对单个元素进行修改。
比如修改第i个元素。
我们先找到[i，i]所在的节点，然后修改它的sum，然后一路向上更新每个祖先的sum即可。
*/
int change(int pos,int v,int 1,int r,int x){
        if( l==r){ 	//找到了要修改的叶子结点
            sum[x]=v;
            return;
        }
        int mid=(1+r)>>1;
        if(pos<=mid)//pos在左子节点
        	change(pos,v,1,mid,x*2);
        else
        	change(pos,v,mid+1,r,x*2+1);
        update(x);//一定要加！因为这条路上的sum值发生了改变
}

性质

节点数：假设线段树处理的数列长度为n，即根节点的区间为[1，n].那么结点数不超过2n个.因此线段树的空间复杂度是0（n）。是完满二叉树(Full Binary Tree)，但一般申请4*n的空间大小
深度：可以看作满二叉树，深度不超过log2(n-1)+1
线段树能把区间上的任意一条长度为L的线段都分成不超过2*log(L)条线段。

注意：

由于链表表示的内存是不连续的，且申请指针比较费时间，所以采用数组矩阵的形式存储。
数组存储也有一点不好，因为线段树并不是真正的完全二叉树。
最后一层可能很空。且空节点的数量可以达到2n个。
因此维护长度为n的序列，用数组存线段树的话，最好要开到4*n的长度，才能保证数组不越界。

形式

线段树

例题：

Q：对于第i个数，我们要统计前面有多少个数大于a[i]。
对每个数都统计一遍加起来即是答案。
假设我们可以对[0，109]建一个线段树（实际上太大了）每次先查询[a[i]+1，109]的区间和，加入答案。

e.g.如果一个值为1，一个值为10^{8，那么要开10}8大小

Solve: 10^9范围太大了，因此我们先要对n个数进行离散化。离散化的过程，就是对n个数进行排序，最小的数赋值为1，第二小的赋值为2，以此类推，这样n个数的取值范围就在[1，n]中了。

e.g.上面的情况，将会把1–>1,10^8–>2,那么只要开长度为2的线段树就够了

// 离散化代码，假设对a[1,2...,n]进行离散化
int cnt=0;
for(int i=1;i<=n;i ++)
    // 另外的数组存储
	bin[++cnt]=a[i];
sort(bin+1,bin+n+1);
// 消重
cnt=unique(bin+1,bin+cnt+1)-bin-1;
for(inti=1;i<=n;i ++)
	a[i]=lower_bound(bin+1,bin+cnt+1,a[i])-bin;

参考：

高中信息学竞赛线段树与树状数组——万门教育

SWPU-ACM每周算法讲堂-线段树入门（一）