1109. 航班预订统计(前缀和+ 公交站+ 树状数组)

class Solution {
    
public:vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    vector<int>res(n,0);//res 表示每个车站人数变化量for(auto book:bookings){
    res[book[0]-1]+=book[2];if(book[1]<n)res[book[1]]-=book[2];}//前面变化的车站（不管增加，减少）会影响到后边，即第i站的人数等于前面i-1站累计变化的与本站变化的人数（本站初始人数为0）。即前缀和for(int i=1;i<n;i++){
    res[i]+=res[i-1];}return res;}
};

class Solution {
    
public:int lowbit(int x){
    return x&(-x);}// int A[n+1];//原数组// int C[n+1];//树状数组vector<int>C;void update(int i, int k){
    while(i<=C.size()-1){
    C[i]+=k;i+=lowbit(i);}}int  getsum(int i){
    int sum=0;while(i>0){
    sum+=C[i];i-=lowbit(i);}return sum;}vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    C.resize(n+1,0);vector<int>res(n,0);//res 表示每个车站人数变化量for(auto book:bookings){
    // A[book[0]]+=book[2];/建原始数组update(book[0],book[2]);if(book[1]<n+1)// res[book[1]+1]-=book[2];update(book[1]+1,-book[2]);}//前面变化的车站（不管增加，减少）会影响到后边，即第i站的人数等于前面i-1站累计变化的与本站变化的人数（本站初始人数为0）。即求前缀和for(int i=1;i<=n;i++){
    res[i-1]=getsum(i);}return res;}
};