树状数组入门(简单的原理讲解)

• 2019 年 10 月 3 日
• 筆記

???????????????

????????????????????????n????????????????

1. ?????m????????1~m????
2. ???????????????

??????????

????
?????????????1~m?????????????1???m?????????n??????????O(n^2)??????????????????????????n?????????O(n)????n????????????????????

• ???????????????
  ?????????A?????????????????????B???????i???A????i??????????????????m??????????????????B?????????n??????????O(n)??????????????????????O(n)???O(n^2)????????????????????????B??????????????????B?????n??????????????O(n^2)??????????

????
???????????????????????????????????????????????????????????????????n???????????O(nlogn)

• ??????????
  
  

??????????n????A?????????????????????C?????C?????????

C1 = A1
C2 = C1 + A2 = A1 + A2
C3 = A3
C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4
C5 = A5
C6 = C5 + A6 = A5 + A6
C7 = A7
C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

???C[i]??????i??????????C[8]????????8???????????8???????i?????????????2^k??k?i???????0?????????????m==8?m==5???????

• 8 = 1000???3?0??k == 3????????2^3 == 8?C8?8????
• 5 = 0101?????0??k == 0????????2^0 == 1?C5??????????A5?

???????m????????m??????A1~Am???????????????C1~C8???????????????????????????????????????????????C??????????????m==7?m==6?sum(i)??????i?????

• m==7 sum(7) = C7 + C6 + C4
  ???????????7?????C[i]??????C4, C6, C7????????????????????
  ?????m?????????????????1?????-1?????????0??
  7?????0111?C7????????0111???1???-1???0110 == 6?C6??????0110??1??-1???0100 == 4?C4???????0100??1??-1???0000??????????????C7?C6?C4??????????m == 7??????
• m==6 sum(6) = C6 + C4
  m == 6?????????2????0110?????????0100?C4??0000???????????????????????

?????????????lowbit(int m)???????????????m?????????1?????????m?????m = m – lowbit(m)??????????1??-1?????????m == 0??????????????Cm????????lowbit?????????

int lowbit(int m){      return m&(-m);  }

??m&(-m)???????????????????????????????????????????????????????13???????1101???-13??????13????????????+1??0010 + 0001 = 0011???1101 & 0011== 0001??????m == 13?????1????2?0?????13 – 0001 == 12???12??lowbit???1100 & 0100 == 0100????????m == 12??????1????2?2?????12 – 0100 == 8???8??lowbit???0100 & 1100 == 0100???m == 8??????2?2????8 – 0100 == 0??????????????13?12?8??sum(13) == C13 + C12 + C8

???????

int ans = 0;  int getSum(int m){      while(m > 0){          ans += C[m];          m -= lowbit(m);      }  }

??n??????????????O(nlogn)
??????????
???????x?????????????value????????????

??x==2?value==5????????A[2]??????????????????A[2]???????A[2]?C[2]?C[4]?C[8]????????value????????????????????????C2???????????C2?A2?????????????C[x]?????????????????????????
?????x????????x?????????????????1???+1?????????????n??

• ???????x==2?????????n==8?x?????????0010?C2?????1?????+1???0100?C4??????1?????+1???1000?C8????????C2?C4?C8????????value????????A[2]??+value??????????

????

void update(int x, int value){      A[x] += value;    //?????A????????????      while(x <= n){          C[x] += value;          x += lowbit(x);      }  }

??n??????????????O(nlogn)

?????????????????????????????C??????????????????????????????????

?????????????A?????????????????????????????A1~An?0????????A[i]????????A[i]????C[i]?????????????????????C???????

• ???????

#include<stdio.h>  #include<string.h>    int a[10005];  int c[10005];  int n;    int lowbit(int x){      return x&(-x);  }    int getSum(int x){      int ans = 0;      while(x > 0){          ans += c[x];          x -= lowbit(x);      }      return ans;  }    void update(int x, int value){      a[x] += value;      while(x <= n){          c[x] += value;          x += lowbit(x);      }  }    int main(){      while(scanf("%d", &n)!=EOF){    //????n == 8          memset(a, 0, sizeof(a));          memset(c, 0, sizeof(c));          for(int i = 1; i <= n; i++){              scanf("%d", &a[i]);     //a[i]????????????????1?2?3?4?5?6?7?8              update(i, a[i]);        //????????????          }          int ans = getSum(n-1);      //??????n-1???? ??28          printf("%dn", ans);      }      return 0;  }