指定された数以上の配列内の要素の数をクエリし、それを更新します

セグメント ツリーを使用すると、配列を正常に更新し、範囲クエリを実行できます。更新することで、既知のデータ構造セグメント ツリーを使用してカウントできるようになります。配列内の要素の数が no 以上です。

• クエリ - x より大きい、または x に類似するアイテムが範囲 [l, r] 内にいくつ存在するかを調べます。

• 範囲 [l, r] がセグメント ツリーの現在のノードによって表されるセグメントを完全に超える場合、0 が与えられます。

• 数えています。区間 [l, r] がセグメント ツリーの現在のノードによって表されるセグメント内に完全に存在する場合、範囲 [l, r] 内の x より大きいかそれに近い要素の数。

• そうでない場合は、現在のノードの左右の子ノードに再帰的に ping を実行し、収集されたカウントの合計数を返します。

• Update - インデックス i の要素に、v の値を追加します。このアップデートには次のアルゴリズムを適用します -

• セグメントツリーの現在のノード表示範囲にインデックスiがない場合は何も行われません。

• インデックス i の値が x 以上の場合、線分ツリーの現在のノードによって表される区間内の x 以上の要素の数を更新します。 i が x 以上である場合は、i をインクリメントしてから、現在のノードの左右の子要素ノードを再帰的に更新します。

• セグメント ツリーのルート ノードで [0, n-1] の範囲でクエリを実行できます。n は合計数です。 x 以上の配列内のエントリの数。

＃＃＃文法＃＃＃

1. セグメント ツリーと配列を最初から作成する -

リーリー

2. 更新(変更)手続きを行う -

リーリー

3.次のクエリ操作を実行します -

リーリー

4. クエリ操作を使用して数量をカウントします。指定された値以上の要素、配列およびセグメント ツリーを更新する更新操作 -

リーリー ＃＃＃アルゴリズム＃＃＃

update を使用して数値を計算する方法は次のとおりです。指定された値以上の配列メンバー -

ステップ 1

- 開始値を保持するサイズ n の配列 A を作成します。

• ステップ 2
- 最小範囲クエリを表示するには、サイズ 4*n のセグメント ツリー T を初期化します。

• ステップ 3
- 関数 build (T, A, 1, 0, n-1) を使用して線分ツリー T を作成します。ここで、build(T, A, v, tl) , tr ) A の値を使用して範囲 [tl, tr] にセグメント ツリー T を作成し、結果を T のノード v に置きます。

• ステップ 4
- サイズ n の配列 C を作成し、指定された数以上の項目数で初期化します。

• ステップ 5
- カウント クエリの範囲合計を表す、開始サイズ 4*n のセグメント ツリー S を作成します。

• ステップ 6
- 関数 build (S, C, 1, 0, n-1) を呼び出します。ここで、build(S, C, v, tl, tr) は線分を作成します。ツリー S 範囲 [tl, tr] については、C の値を使用し、結果を S のノード v に保持します。

• ステップ 7
- 各「x 以上の要素をカウントする」クエリに応答します -

• 配列 A の範囲 [l, r] 内の最小値を見つけるには、関数 query(T, 1, 0, n-1, l, r) を呼び出します。結果が m であるとします。

  m が x 以上の場合、関数 query(S, 1, 0, n-1, l, r) を使用して合計数を取得します。配列 C の区間 [l, r] 内の x 以上のエントリの数。結果を c とします。

そうでない場合は、c を 0 に設定します。

ステップ 8

- 各タイプの変更「A[i] の値を v に設定する」 -

• 範囲 [tl,tr] 内の線分ツリー T のノード v を更新し、関数 update(T,v,tl,tr,i,val) を呼び出します。ここで、update(T,v,tl,tr) , i,val) は、インデックス i の値を val に設定することにより、セグメント ツリー T のノード v を変更します。

  関数 update(S, 1, 0, n-1, i, (v >= x)) を使用して、範囲 [tl, tr] の線分ツリー ノード v を更新します。ここで、update(S, v 、tl、tr、i、val) x 以上の項目の数に val を加算して、ノード v を更新します。

ステップ 9

- ステップ 7 と 8 をもう一度繰り返します。

• 従うべき方法

方法1

この例では、配列を表す int 型のベクトルと、カウントしたいエントリ数以上の int 型のしきい値を定義します。次に、関数 counttheElements を使用して、初期配列としきい値以上の要素の数を生成します。

updatetheElement 関数は、配列、更新する要素のインデックス、要素の新しい値をパラメーターとして受け取り、配列内の要素を更新するために使用されます。最後に、再度 counttheElements メソッドを使用して、変更された配列と、しきい値以上の新しい要素数を出力します。

例 1

リーリー ＃＃＃出力＃＃＃ リーリー

方法-2

各クエリの機能はカウントすることです。 query[i] 以上の配列 (項目) を取得し、それらの値をすべて M だけ減分し、更新された配列に対して問題の残りを実行します。入力は 2 つの配列、array[] と query[] で、それぞれサイズが N と Q です。

まず配列 [] を昇順に並べ替えます。

最初の位置にある要素が query[i] 以上である要素 (l など) を検索します。

そのような要素がない場合は、応答として 0 を返します。それ以外の場合、応答は N - l になります。

最后一步是从提供的范围内的每个元素中减去 M，并将区间 l 中的线段树更改为 N - 1。

示例 2

#include <bits/stdc++.h>
using namespace std;

void build(vector<int>& tosum, vector<int>& a, int l, int r, int rlt){
   if (l == r) {
      tosum[rlt] = a [l - 1];
      return;
   }
   int m = (l + r) >> 1;
   build (tosum, a, l, m, rlt << 1);
   build (tosum, a, m + 1, r, rlt << 1 | 1);
}
void push(vector<int>& tosum, vector<int>& toadd, int rlt, int ln, int rn){
   if (toadd[rlt]) {
      toadd [rlt<< 1] += toadd[rlt];
      toadd [rlt << 1 | 1] += toadd[rlt];
      tosum [rlt<< 1] += toadd[rlt] * ln;
      tosum [rlt << 1 | 1] += toadd[rlt] * rn;
      toadd[rlt] = 0;
   }
}
void update(vector<int>& tosum, vector<int>& toadd, int L, int R, int C, int l,int r, int rlt){
   if (L <= l && r <= R) {
      tosum[rlt] += C * (r - l + 1);
      toadd[rlt] += C;
      return;
   }
   int m = (l + r) >> 1;
   push (tosum, toadd, rlt, m - l + 1,
   r - m);
   if (L <= m)
      update (tosum, toadd, L, R, C, l, m,
      rlt << 1);
   if (R > m)
      update (tosum, toadd, L, R, C, m + 1, r,
      rlt << 1 | 1);
}
int query(vector<int>& tosum,
   vector<int>& toadd,
   int L, int R, int l,
   int r, int rlt){
   if (L <= l && r <= R) {
      return tosum[rlt];
   }
   int m = (l + r) >> 1;
   push (tosum, toadd, rlt, m - l + 1,
   r - m);
   int ans = 0;
   if (L <= m)
   ans += query (tosum, toadd, L, R, l, m,
   rlt << 1);
   if (R > m)
   ans += query (tosum, toadd, L, R, m + 1, r,
   rlt << 1 | 1);
   return ans;
}
void sequMaint(int n, int q,vector<int>& a,vector<int>& b,int m){
   sort(a.begin(), a.end());
   vector<int> tosum, toadd, ans;
   tosum.assign(n << 2, 0);
   toadd.assign(n << 2, 0);
   build (tosum, a, 1, n, 1);
   for (int i = 0; i < q; i++) {
      int l = 1, r = n, pos = -1;
      while (l <= r) {
         int m = (l + r) >> 1;
         if (query (tosum, toadd, m, m, 1, n, 1)
         >= b[i]) {
            r = m - 1;
            pos = m;
         }
         else {
            l = m + 1;
         }
      }
      if (pos == -1)
      ans.push_back(0);
      else {
         ans.push_back(n - pos + 1);
         update (tosum, toadd, pos, n, -m,
         1, n, 1);
      }
   }
   for (int i = 0; i < ans.size(); i++) {
      cout << ans[i] << " ";
   }
}
int main (){
   int A = 4;
   int B = 3;
   int C = 1;
   vector<int> array = {1, 2, 3, 4};
   vector<int> query = {4, 3, 1};
   sequMaint(A, B, array, query, C);
   return 0;
}

输出

1 2 4

结论

综上所述，线段树可以成功地用于计数。数组中大于或等于固定值并进行更新的元素的数量。我们使用惰性传播来更新线段树，而不是更新每个节点。对节点的更新是在延迟传播期间完成的，直到需要为止。总的来说，我们可以有效地数出没有。通过使用具有延迟传播的线段树，数组中大于或等于特定值且发生变化的元素。

以上が指定された数以上の配列内の要素の数をクエリし、それを更新しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。