問題があり、フェンウィック ツリーで解決できるかどうかわかりません。問題は次のとおりです。元の配列 a = [8,4,7,0] があります。ここで、配列を反復処理し、各ステップで次のような並べ替えられたサブ配列に関心があります: [8]、[4,8]、[4,7,8]、[0,4,7、 8]。現在の数値を挿入する反復の各ステップで、挿入した数値よりも大きいすべての数値の合計を知りたいです。したがって、上記の例では、次のようになります。
- [8]; 合計 = 0 挿入された数値 (8) より大きいすべての数値の合計は 0 であるため
- [4,8]; 合計 = 8 挿入された数値 (4) よりも大きいすべての数値の合計は 8 であるため
- [4,7,8]; 合計 = 8 挿入された数値 (7) よりも大きいすべての数値の合計は 8 であるため
- [0,4,7,8]; 合計 = 19 挿入された数値 (0) よりも大きいすべての数値の合計は 19 であるため
上記の例は単なる説明のためのものであり、元の配列ははるかに大きくなる可能性があるため、そのような合計を効率的に計算することが非常に重要になります。これを効率的に解決する方法について何か提案はありますか?