木の形の配列——逆の順序を求めて個数に対して(初心者はすべて理解することができます)

ネット上でいくつかのブログをめくって、大体木の配列に対して逆の順序を求める説明が足りないと感じて、あれらのブログ、もっと多くすでに逆の順序をマスターした人に復習して使うようです.初心者は、瞑想するかもしれません.次に、初心者の立場から、木の配列から逆の順序を求めることを説明します.必要な先行知識は、セグメント配列の基本的な応用のみです.単点更新、区間クエリー、lowbitを求めます.ツリー配列の基本コードを貼り付けます.lowbitを求める

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

シングルポイント更新

void update(int x,int y,int n){
    for(int i=x;i<=n;i+=lowbit(i))    //x ,y ,n 
        c[i] += y;
}

区間クエリー

int getsum(int x){
    int ans = 0;
    for(int i=x;i;i-=lowbit(i))
        ans += c[i];
    return ans;
}

次に、正題逆シーケンス対の原理を開始する.一組の数において、ia[j]の場合、これは逆シーケンス対のセットである.我々は一般的に逆シーケンス対を求める方法で,各数に対して,その後ろにあるそれより小さい数を求める.コードは次のとおりです.

int ans=0;
for(int i=1;i<=n;i++)
{
	for(int j=i+1;j<=n;j++)
	{
		if(ap[i]>ap[j])ans++;
	}
}

時間の複雑さは明らかにn^2なので、もっと速い方法があるのではないでしょうか.木の配列を使うことです.木の配列がどのような問題を解決することができて、ある区間の数の和を求めて、私たちは逆の順序の対を求める問題をこの方向に転化することができますか?
逆順序ペアを別の角度で見てみましょう.各数に対して、前の数と逆順序ペアを形成するか、後ろの数と逆順序ペアを形成する可能性があります.では、簡単に説明します.各数について、逆順対の2番目の数の逆順対としてのみ考慮し、このような逆順対を加算すると、実際には総逆順対の数になります.なぜなら、各逆シーケンスペアには2つの要素があり、最初の数、2番目の数があるからです.逆順対の2番目の数の場合をすべて考慮し,実際にはすべての逆順対を考慮した.
どうやって木の配列に変換するのでしょうか.例を挙げてみましょう.例えば、この配列が5 3 4 2 1 7で最初に5を挿入し、単点更新5という位置+1を行い、区間1から4の数を問い合わせると、0を逆順に加算します.1-0-1=0(i番目の挿入-この数の前の数-そのもの)この数は、その前に挿入され、右側の数です.間違いなく、この数を2番目の数とする逆順です.その前に挿入された数は、その数が計算されるときに含まれます.完全に5を1回挿入し、逆シーケンスを加算します(1-0-1).3を挿入し、逆順に加算します(2-0-1).4を挿入し、逆順に加算します(3-1-1).2を挿入し、逆順に加算します(4-0-1).1を挿入し、逆順に加算します(5-0-1).7を挿入し、逆順に加算します(6-5-1).コードは以下の通りです.
シングルポイント更新

void update(int x,int n){
    for(int i=x;i<=n;i+=lowbit(i))    //x n 
        c[i] ++;
}

区間クエリー

int getsum(int x){
    int ans = 0;
    for(int i=x;i;i-=lowbit(i))
        ans += c[i];
    return ans;
}

統合コード

//  
int ap[maxn+1]={0};
//  
int c[maxn+1]={0};
int ans=0;
for(int i=1;i<=n;i++)
{
	scanf("%d",&ap[i]);
	update(ap[i],n);
	ans+=(i-getsum(ap[i]-1)-1);
}

このような時間複雑度はnlgnである.しかし、いくつかの問題があるのではないでしょうか.一般的に言えば、要求数が10^9未満であれば、こんなに大きな配列を開いているのではないでしょうか.爆発したに違いありません.どうすればいいですか.用語は離散化しているようで、私たちはもっと簡単な数で相対的な大きさを表すことを意味します.例えば1234 1526 128783 121 2343 23432相対サイズの代わりに2 3 5 1 4 6を用いることができ、求めた逆シーケンス対個数は変わらない.もちろん、このような時間の複雑さは高すぎる.もう1つの方法は、構造体で(1234、配列の下のラベル1と合わせて)他のいくつかの数も、1234 1526 128783 121 2343 234332をソートして、得られたサブキーワード4 1 2 5 3 6を見つけることができ、その逆順序の個数は元の数1234 1526 128783 121 2343 234332と同じであることがわかります.なぜかというと、1234 1526 128783 121 2343 234323432 1 2 3 4 5 6推測1:上の配列の任意の2つの数が交換されると、逆シーケンス対が何個減少し、下の数が何個の逆シーケンス対を加えるかを見てみましょう.すべての上の逆順ペアに下の逆順ペアを加えると、定値に等しくなります.推測2:対称性は,上を並べ替えて下,下を並べ替えて上を得る.1234 1526,128783,121,2343,234,432 1 2 3,345 6の順序付けにより、121,1234,1526,2343,128783,234,432,432,342,342,342,342,343,236が得られた.相対変換1 2 3 4 5 6 2343 121 1234 128783 1526 234432が行われる.押していないので、後で実力があってから補充して、みんながコメントして助けてくれることを望んでいます.