HDU 1166 敌兵布阵树状数组||线段树

题目大意：

给定n个数的区间N<=50000，还有Q个询问（Q<=40000）求区间和。

每个询问可能增加点k x的值或者减少x。

思路：

原题描述很有爱啊~

树状数组好久没写了~

依旧很熟练，WA了两三次，第一次因为没有输出case，。。。。。。。第二次发现多组数据没有初始化。T^T

~像这种单点修改求区间和的还是用树状数组比较简单~

树状数组：

#include
  
   
#include
   
     const int MAXN=50000+10; int sum[MAXN]; inline int lowbit(int x) { return x&-x; } int getsum(int x) { int ans=0; while(x>0) { ans+=sum[x]; x-=lowbit(x); } return ans; } void add(int x,int v) { while(x
    
     线段树：
      
     #include
      
       
#include
       
         const int MAXN=50000+10; int sum[MAXN<<2],a[MAXN]; void build(int k,int L,int R) { if(L==R) sum[k]=a[L]; else { int m=(L+R)/2; build(k*2,L,m); build(k*2+1,m+1,R); sum[k]= sum[k*2]+sum[k*2+1]; } } int getsum(int k,int L,int R,int a,int b) { int m=(L+R)/2,ans=0; if(a<=L && R<=b) return sum[k]; if(a<=m) ans+=getsum(k*2,L,m,a,b); if(m

HDU 1166 敌兵布阵 树状数组||线段树