問題タブ [fenwick-tree]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
data-structures - クエリと更新を使用して mod sum を効率的に計算するにはどうすればよいですか
配列 A(A[1..n]={1,2,3} など) が与えられた場合、次の 2 つのクエリが必要です。
1) Update(idx,val) : A[idx]=val の値を更新
2) intクエリ(MOD).....
MOD のすべての可能な値としてインデックスを持つフェンウィック ツリーを考えましたが、問題は、A[i]%MOD が A[i] ごとに異なる可能性があるため、一定の更新がないことです。効率的に行うにはどうすればよいですか？
algorithm - フェンウィック ツリーの実装により TLE が得られる
サンプル入力:
5 6
3 1 4 1 5
1 2 4 8 16
2 5 2
1 3 5
2 3 4
2 1 4
2 5 1
2 3 3
サンプル出力:
22
13
-1
22
5
フェンウィック ツリーを実装して、ツリーのパス上のノードの値の合計を計算するこの質問を試みています。フェンウィック ツリーは DFS 配列に実装されており、「イン」時間中はノード値を正として、「アウト」時間中はノード値を負として格納します [(参照されたアルゴリズムへのリンク)](https://codeforces.com/blog/entry /78564)。
h[i] > h[j] (高さ) の場合、ノード i からノード j へのエッジがあり、方向を変えるエッジは存在しません。つまり、i の増加または減少にエッジを追加する必要があります。各ノードの値はベクトル a に格納され、更新できます。だから私は両方向から2本の木を構築しました。
プログラムは、サンプル テスト ケースに対して適切に実行されます。しかし、制約 N, Q <= 1000 でも TLE が得られます。この問題の元の制約は N, Q <= 2*10 5です。
Pl ベクトルは、左から右に根を張るツリーの親を格納します。Pr は、右から左に根ざしたツリーの親を格納します。同様に、arrayl と arrayr (DFS 配列)、timer と timel (開始時刻と終了時刻の配列) を作成しました。
クエリには 2 つのタイプ
があります。パスが存在するかどうかを尋ねてから、ノードの最大合計を見つけます。
または、特定のノードの値を更新します。
プログラムの順序を計算すると、O((N+Q)logN)程度になりました。私が間違っている？コードのどこが間違っていますか?
参考文献:動的計画法
を必要とする山登り問題
https://www.geeksforgeeks.org/next-greater-element/
さらに説明が必要な場合は、コメントを追加してください。関連情報を可能な限り掲載しました。
kotlin - kotlinで変更可能なリストのサイズ制限を増やす方法は?
フェンウィック ツリー データ構造を使用して、コードフォースに関するマルチセットの質問 ( https://codeforces.com/contest/1354/problem/D )を解決しようとしていました。サンプル テスト ケースには合格しましたが、サブミット後にメモリ制限エラーが発生しました。テストケースは以下のとおりです。(基本的に、テストケースは次のとおりです。
1000000 1000000
1......................1 //10^6 回
-1..........-1 //10^6 回)。
IDE で同様のテストケースを試したところ、以下のエラーが発生しました。(上記と同様に、私が提供したテストケースは次のとおりです。
1000000 1
1......................1 //10^6 回
-1
)
スレッド「メイン」での例外 java.lang.IndexOutOfBoundsException: java.base/jdk.internal の java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64) で、長さ 524289 の範囲外のインデックス 524289。 java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248) の util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70) 373) MultisetKt.main(multiset.kt:47) で java.base/java.util.ArrayList.get(ArrayList.java:426) で MultisetKt.main(multiset.kt) で
これが私のコードです：
これは、BITlist が 10^6 要素を格納できないためだと思いますが、確かではありません。コードにどのような変更を加える必要があるか、また将来そのような場合に対処する方法についての追加のアドバイスを教えてください。
前もって感謝します ：）