C言語ツリー配列の例を詳しく説明します。

C言語ツリー配列の例を詳しく説明します。
最近木の配列を勉強しましたが、このデータ構造が不思議ですね。
まず、彼女の定数は線分樹より小さいです。次に彼女の複雑さも線分樹よりずっと低いです。
彼女を上手に使いこなす必要があります。
樹状配列の基礎知識と原理についてネットで検索してみたら、詳しくは説明しません。樹状配列の応用について話しましょう。
1,単に修正して、区間と

#define lowbit(x) (x&-x) //   x          y ,   lowbit(x) == 2^y 
void Update(int i,int v) //          
{
  while(i <= n)
  {
    c[i] += v ;
    i += lowbit(i) ;
  }
}

inline int Sum(int i)  //      
{
  int res = 0 ;
  while(i > 0)
  {
    res += c[i] ;
    i -= lowbit(i) ;
  }
  return res ;
}

2、区間修正、単点検索
ここでは差分の思想を使います。
差分数グループc[]を作成し、c[i]=a[i]-a[i-1](a[i]は本来のi番目の個数を表します。)
a[i]=（a[i]-a[i-1]）+（a[i-1]-a[i-2]）+（a[2]-a[1]）+a[1]
         = c[i]+c[i-1]+…+c[2]+c[1]
したがって、単一のポイントの検索は、区間の合計となります。
区間修正はどうすればいいですか？
このような例を見ます。
a 1 3 4 5 7 10
c 1 2 1 1 2 3
私たちが区間[2,4]に2を加えると、
a 1 5 6 9 10
c 1 4 1 1 2 1
c[2]とc[5]だけの数値が変わったことが分かります。原理もとても良くて、区間内の前後の要素差は不変です。（区間の最初の元素と前の元素の差）と（区間後の最初の元素と区間の末尾要素の差）だけが変わりました。だから区間修正の問題は単点修正の問題になりました。

  for(int i=1;i<=n;i++)
  {
    a[i] = read() ;
    Update(i,a[i]-a[i-1]);
  } 
/*  int x=0,y=0;    //              （        ）
  for(int i=1;i<=n;i++)
  {
    if(i%2)
    {
      x = read() ;
      Update(i,x-y);
    }
    else
    {
      y = read() ;
      Update(i,y-x) ;
    }
  } */
  int ii ;
  int k,x,y;
  for(int i=1;i<=m;i++)
  {
    ii = read() ;
    if(ii == 1)
    {
      x = read() ; y = read() ; k = read() ;
      Update(x,k);
      Update(y+1,-k);
    }
    if(ii == 2)
    {
      x = read() ;
      printf("%d
",Sum(x));
    }
  }

（洛谷には対応するテンプレートがあります。P 374とP 368）
上記は樹状配列の最も基本的な二つの応用です。今後もっと深く勉強してから更新します。
 疑問があれば、メッセージをお願いします。あるいは、当駅のコミュニティで交流して討論してください。ありがとうございます。