segment-tree

0熱

1答えて

RMQを実行するためのセグメントツリーを構築しようとしています。どういうわけか、私はどの範囲を照会しても0を返します。たとえば、私の配列は[ 1,2,3,4,5,6,7,8,9,10 ]です。インデックス3〜5 RMQ 4.与えるべきである。しかし、私のコードは0 私のコードを出力し続ける： #include<bits/stdc++.h> using namespace std; #de

0熱

1答えて

私は次のような問題を解決しようとしています（更新やクエリを含む）の範囲の重みk

で項目の数を探す：整数の重みを持つ項目の配列を考えると（任意の順序）、我々は持つことができます2つの可能な操作：クエリ：の範囲xからyまでの重みkの項目の数を出力します。更新：Vに一定インデックスの項目の重みを変更例：配列を指定：[1,2,3,2,5,6,7,3 ] を、我々は3に、インデックス1から重量2と項目数を照会した場合、我々は2の重みを持っているために、インデックス2の要素

1熱

3答えて

境界は

が、私はこの問題を解決するための効率的な方法を知りたいの長方形：、左上と右下の隅を与えられたN個の長方形を考えると、の周囲を見つけてくださいN個の矩形の和集合。私はO(N^2)アルゴリズムを持っており、それはあまりにも遅いですので、より効率的なアルゴリズムを見つけてください。あなたはその座標値は正の整数未満100000 EDITされると仮定することができる。例えば、この場合には、周囲が30

0熱

1答えて

ツリー上のパスでクエリに答えるには？

私は配列を持っていて、インデックスiからjまでのすべての要素の合計を見つけるようなクエリに答える必要があります。ノードiからjへのパスに対してこのようなクエリに答えるのと同じように、 iからjまで存在する唯一の経路）。 LCA私はそれを線形配列に分解してセグメントツリーを使用する範囲最小クエリを使用して検索する方法を知っていますが、サムクエリに対しては変更できません。それ、どうやったら出来るの？

0熱

1答えて

永続セグメントツリーとは何ですか？どのように使用しますか？

私は永続的なセグメントツリーを使って解決できる多くの問題に遭遇しましたが、私はこの概念を理解できないようです。私はいくつかのリソースを見つけましたが、まだ理解できません。

1熱

2答えて

範囲ツリー内のパスのクエリ

私はコンテスト（これは終わった）でこの質問に出くわしました。私は時間効率のよいアルゴリズムを考えることができません。 N（< = 10^5）ノードのルートツリーが与えられました。最初にすべてのノードは値0を持つ。ツリーのM個の更新（< = 10^5）が追加される。x yを加える - ノードxにyを加える。 AddUp x y - yをxの親、xの親、xの親の親をuptill Rootに追加します

0熱

1答えて

間違った回答 - バグを見つけることができません - 範囲最小クエリセグメント木に

を使用して、私はthis疑問を解決しようとしたセグメントの木の基本を理解した後https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/ を通じてセグメントツリーを学ぶしようとしています。しかし、1つのテストケースしか渡さ

1熱

1答えて

タイプl、r、kの質問に答えるには、少なくともk回発生する範囲l〜rの配列の要素の数を見つけるか？

l〜rの範囲で少なくともk回発生する配列内の要素の数を見つけるl、r、k型の問合せに対する答えを計算する方法は？ Moのアルゴリズムの使い方

0熱

1答えて

Cプログラムのすべての関数で配列にアクセスするには？

競合コーディングの問題のセグメントツリーを作成しようとしていますが、このツリーは配列を使って表現されています。私はrangeMinQueryとupdateTreeという関数を持っています。これらの関数は配列上で中間のジョブを実行します。私は関数を使って前記配列を操作する方法を理解することができません。 #include <stdio.h> #include <stdlib.h> #define

1熱

1答えて

セグメントツリーで範囲更新を適用する方法は？

私はすでにパーシスタンスセグメントツリーを作っていますが、現在はあるインデックスからあるインデックスへの範囲の更新があります。永続性セグメントツリーを複雑さを少なくして更新するには？私はちょうど