Fragen Sie die Anzahl der Elemente in einem Array ab, die größer oder gleich einer bestimmten Zahl sind, und aktualisieren Sie sie

Mit Hilfe von Segmentbäumen können Arrays erfolgreich aktualisiert und Bereichsabfragen durchgeführt werden. Durch die Aktualisierung können wir die bekannte Datenstruktur des Segmentbaums zum Zählen verwenden. Die Anzahl der Elemente im Array, die größer oder gleich „Nein“ ist.

• Abfrage – Finden Sie heraus, wie viele Elemente größer oder ähnlich x im Bereich [l, r] vorhanden sind.

• Gegeben 0, wenn der Bereich [l, r] vollständig über das Segment hinausgeht, das durch den aktuellen Knoten des Segmentbaums dargestellt wird.

• Zählen. Die Anzahl der Elemente im Bereich [l, r], die größer oder ähnlich x sind, wenn das Intervall [l, r] vollständig innerhalb des Segments liegt, das durch den aktuellen Knoten des Segmentbaums dargestellt wird.

• Wenn nicht, pingen Sie rekursiv den linken und rechten untergeordneten Knoten des aktuellen Knotens an und geben Sie die Gesamtzahl der erfassten Zählungen zurück.

• Update – Fügen Sie für das Element am Index i den Wert von v hinzu. Wir wenden den folgenden Algorithmus auf dieses Update an –

• Wenn der aktuelle Knotenanzeigebereich des Segmentbaums keinen Index i hat, wird keine Operation ausgeführt.

• Wenn der Wert des Index i größer oder gleich x ist, aktualisieren Sie die Anzahl der Elemente, die größer oder gleich x im Intervall sind, das durch den aktuellen Knoten des Liniensegmentbaums dargestellt wird. Wenn der Wert des Index i größer als ist oder gleich x, erhöhen Sie es und aktualisieren Sie dann rekursiv den aktuellen Knoten. Die linken und rechten untergeordneten Elementknoten.

• Wir können Abfragen im Bereich [0, n-1] im Wurzelknoten des Segmentbaums ausführen, wobei n die Gesamtzahl ist. Die Anzahl der Einträge im Array größer oder gleich x.

Grammatik

1. Erstellen Sie Segmentbäume und Arrays von Grund auf -

int M; 
int Z[M]; 
int TreE[4*M]; 
BUILD (1, 0, M-1, Z, TreE); 

2. Führen Sie den Update-(Änderungs-)Vorgang durch -

Void change (int NoDe, BeGiN,EnD,IdX,VaL,TreE []) {
   if (BeGiN==EnD) {
      Z[IdX]=VaL;
      TreE[NoDe]=VaL;
   } else {
      int MiD= (BeGiN + EnD)/2;
      if (BeGiN<=IdX && IdX<=MiD)
         change (2*NoDe, BeGiN, MiD, IdX, VaL, TreE);
      else
         change (2*NoDe+1, MiD+1, EnD, IdX, VaL, TreE);
      TreE[NoDe] = TreE[2*NoDe] + TreE[2*NoDe+1];
   }
}

3. Führen Sie die folgenden Abfragevorgänge aus -

int QUERY(int NoDe, BeGiN, EnD, L, R, K, TreE []) {
   if(sTaRT > EnD || BeGiN > R || EnD < L)
      return 0;
   if(BeGiN == EnD)
      return A[BeGiN] >= K;
   int MiD = (BeGiN + EnD) / 2;
   return QUERY(2*NoDe, BeGiN, MiD, L, R, K, TreE) + QUERY (2*NoDe+1, MiD+1, EnD, L, R, K, TreE);
}

4. Verwenden Sie Abfrageoperationen, um Mengen zu zählen. Elemente größer oder gleich dem angegebenen Wert, Aktualisierungsvorgang zum Aktualisieren von Arrays und Segmentbäumen -

int IdX, VaL; 
change(1, 0, n-1, IX, VaL, TreE);
int L, R, K; 
int count = QUERY(1, 0, M-1, L, R, K, TreE);

Algorithmus

Mit dem Update gibt es hier eine Möglichkeit, die Zahl zu berechnen. Array-Mitglieder größer oder gleich dem angegebenen Wert -

• Schritt 1 – Erstellen Sie ein Array A der Größe n, um den Startwert zu speichern.

• Schritt 2 – Um die Mindestbereichsabfrage anzuzeigen, initialisieren Sie einen Segmentbaum T der Größe 4*n.

• Schritt 3 – Erstellen Sie einen Segmentbaum T mit der Funktion build (T, A, 1, 0, n-1), wobei build(T, A, v, tl, tr ) die Werte in A verwendet um den Bereich [ tl, tr] zu erstellen und das Ergebnis in den Knoten v von T einzufügen.

• Schritt 4 – Erstellen Sie ein Array C der Größe n und initialisieren Sie es mit einer Anzahl von Elementen, die größer oder gleich der angegebenen Anzahl ist.

• Schritt 5 – Erstellen Sie einen Segmentbaum S mit der Startgröße 4*n, um die Bereichssumme der Zählabfrage darzustellen.

• Schritt 6 – Rufen Sie die Funktion build (S, C, 1, 0, n-1) auf, wobei build(S, C, v, tl, tr) einen Liniensegmentbaum S für den Bereich [tl, tr], Verwenden Sie den Wert in C und behalten Sie das Ergebnis im Knoten v von S.

• Schritt 7 – Beantworten Sie jede Abfrage „Elemente größer oder gleich x zählen“ –

Um den Mindestwert im Bereich [l, r] von Array A zu finden, rufen Sie die Funktion query(T, 1, 0, n-1, l, r) auf. Angenommen, das Ergebnis ist m.

Wenn m größer oder gleich x ist, verwenden Sie die Funktion query(S, 1, 0, n-1, l, r), um die Gesamtzahl zu erhalten. Die Anzahl der Einträge im Intervall [l, r] von Array C, die größer oder gleich x sind. Das Ergebnis sei c.

Wenn nicht, setzen Sie c auf 0.

• Schritt 8 – „Setzen Sie den Wert von A[i] auf v“ bei jeder Typänderung –

Aktualisieren Sie den Knoten v des Liniensegmentbaums T im Bereich [tl,tr] und rufen Sie die Funktion update(T,v,tl,tr,i,val) auf, wobei update(T,v,tl,tr,i , val) ändert den Knoten v des Segmentbaums T, indem der Wert am Index i auf val gesetzt wird.

Verwenden Sie die Funktion update(S, 1, 0, n-1, i, (v >= x)), um den Liniensegmentbaumknoten v im Bereich [tl, tr] zu aktualisieren, wobei update(S, v, tl , tr, i, val) aktualisiert Knoten v, indem val zur Anzahl der Elemente hinzugefügt wird, die größer oder gleich x sind.

• Schritt 9 – Wiederholen Sie die Schritte 7 und 8 noch einmal.

Zu befolgende Methode

Methode 1

Im Beispiel definieren wir einen Vektor vom Typ int, der unser Array darstellt, und einen Schwellenwert vom Typ int, der größer oder gleich der Anzahl der Einträge ist, die wir zählen möchten. Verwenden Sie dann die Funktion „counttheElements“, um das anfängliche Array und die Anzahl der Elemente zu generieren, die größer oder gleich dem Schwellenwert sind.

Die Funktion

updatetheElement akzeptiert ein Array, den Index des zu aktualisierenden Elements und den neuen Wert des Elements als Parameter und wird dann zum Aktualisieren der Elemente im Array verwendet. Abschließend verwenden wir erneut die Methode counttheElements, um das geänderte Array und die neue Anzahl von Elementen auszugeben, die größer oder gleich dem Schwellenwert sind.

Beispiel 1

#include <iostream>
#include <vector>
using namespace std;
void updatethenumber(vector<int>& ara, int index, int NEWValues) {
   ara[index] = NEWValues;
}
int countthenumber(vector<int>& ara, int threshold) {
   int cont = 0;
   for (int i = 0; i < ara.size(); i++) {
      if (ara[i] >= threshold) {
         cont++;
      }
   }return cont;
}
int main () {
   vector<int> ara = {3, 6, 2,8, 4, 7} ;
   int threshold = 5;
   cout << "Initial array: ";
   for(int i = 0;i < ara.size();i++) {
      cout << ara[i] << " ";
   }cout<<endl;
   cout<<"Number of elements >= "<<threshold<< ": ";
   cout<<countthenumber(ara, threshold)<<endl;
   cout<<"Updating element at index 2 to value 9..."<<endl;
   updatethenumber(ara,2,9) ;
   cout<<"Updated array: " ;
   for(int i = 0;i<ara.size();i++) {
      cout<<ara[i]<< " ";
   } cout<<endl ;
   cout<<"Number of elements >= " << threshold << ": " ;
   cout<<countthenumber(ara, threshold)<<endl;
   return 0;
}

Ausgabe

Initial array: 3 6 2 8 4 7 
Number of elements >= 5: 3
Updating element at index 2 to value 9
Updated array: 3 6 9 8 4 7 
Number of elements >= 5: 4

Methode-2

Die Funktion jeder Abfrage besteht darin, zu zählen. Array (Elemente) größer oder gleich query[i], dekrementieren Sie alle diese Werte um M und führen Sie den Rest des Problems auf dem aktualisierten Array aus. Die Eingaben sind zwei Arrays, array[] und query[], mit den Größen N bzw. Q.

Sortieren Sie zunächst das Array[] in aufsteigender Reihenfolge.

Suchen Sie das Element, dessen Element an der ersten Position größer oder gleich query[i] ist, z. B. l.

Wenn es kein solches Element gibt, geben Sie 0 als Antwort zurück. Andernfalls lautet die Antwort 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

结论

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

Das obige ist der detaillierte Inhalt vonFragen Sie die Anzahl der Elemente in einem Array ab, die größer oder gleich einer bestimmten Zahl sind, und aktualisieren Sie sie. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!