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

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

王林

リリース： 2023-09-05 08:25:12

転載

911 人が閲覧しました

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

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

ステップ 2
ステップ 3
ステップ 4
ステップ 5
ステップ 6
ステップ 7
配列 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

範囲 [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

従うべき方法

この例では、配列を表す 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;
}

ログイン後にコピー