search
HomeBackend DevelopmentC++Using a tree array (offline query), calculate the number of elements greater than K in the range L to R

Using a tree array (offline query), calculate the number of elements greater than K in the range L to R

In the field of computer science, we have to deal with large data sets, which include query select and update operations. Performing these operations in real-time with low time complexity is a challenging task for developers.

Using Fenwick trees is an effective way to solve these range-based query problems.

Fenwick Tree is a data structure that can efficiently update elements and calculate the prefix sum of numbers in a table. It is also called a binary index tree.

In this article, we will discuss how to use Fenwick tree to find the number of elements greater than K in the range L to R.

Input and output scenarios

Suppose you have an array with N elements, and you want to find the number of elements in the array that are greater than K in the range L to R.

Input: 
arr = {1, 15, 12, 13, 6, 18, 14, 10, 23, 41, 16, 9}
N = 11, K = 17, L = 1, R = 8
Output: 
2

What is offline query?

Offline query is a query operation performed on a predetermined data set. In other words, these operations are performed only on those datasets that are not further modified while processing the query.

Use Fenwick Tree

Here we will use a Fenwick tree, which has vectors at each node containing all the elements of the array in order. We then use binary search to answer each query and count the number of elements.

  • Create two functions, updateTree() and total(), for updating and retrieving the prefix sum in BIT respectively.

  • Next, create another function that will count elements in the range L to R that are greater than "K". This function accepts the input values ​​"arr", "N", "L", "R" and "K" ".

  • The count is calculated by subtracting the cumulative sum of K from the cumulative sum of the maximum range N.

To exclude out-of-range elements, subtract the cumulative sum of L-1 (if L is greater than 1).

Example

#include <iostream>
#include <vector>
using namespace std;

// Updating the Fenwick Tree
void updateTree(vector<int>& BIT, int index, int value) {
   while (index < BIT.size()) {
      BIT[index] += value;
      index += index & -index;
   }
}

int total(vector<int>& BIT, int index) {
   int result = 0;
   while (index > 0) {
      result += BIT[index];
      index -= index & -index;
   }
   return result;
}

// Counting the number of elements
int elementsGreaterThanK(vector<int>& arr, int N, int K, int L, int R) {
   vector<int> BIT(N+1, 0);

   for (int i = L; i <= R; i++) {
      updateTree(BIT, arr[i], 1);
   }

   int count = total(BIT, N) - total(BIT, K);
   if (L > 1) {
      count -= total(BIT, L-1);
   }
   return count;
}

int main() {
   vector<int> arr = {0, 5, 2, 3, 6, 8, 7, 1, 8, 4, 6, 9};
   int N = 11; // Total range of values
   int K = 4; // Highest value
   int L = 1; // Start index of the range
   int R = 8; // End index of the range

   int count = elementsGreaterThanK(arr, N, K, L, R);
   cout << "Number of elements greater than " << K << " in the range [" << L << ", " << R << "]: " << count << endl;

   return 0;
}

Output

Number of elements greater than 4 in the range [1, 8]: 5

alternative method

Here we will create a separate vector to store the query. Each query consists of two variables, index and val. index is used to store the position in the array, and val is used to store the value of the element at that index. This approach enables developers to perform a variety of query operations. Additionally, we use BIT to count the number of elements greater than K for each query.

Example

#include <iostream>
#include <vector>
using namespace std;
struct Query {
   int index;
   int val;
};

void updateTree(vector<int>& BIT, int index, int value) {
   while (index < BIT.size()) {
      BIT[index] += value;
      index += index & -index;
   }
}

int total(vector<int>& BIT, int index) {
   int result = 0;
   while (index > 0) {
      result += BIT[index];
      index -= index & -index;
   }
   return result;
}

vector<int> elementsGreaterThanK(vector<int>& arr, vector<Query>& queries, int K) {
   int N = arr.size();
   vector<int> BIT(N+1, 0);
   vector<int> result;

   for (int i = 0; i < N; i++) {
      updateTree(BIT, i+1, (arr[i] > K) ? 1 : 0);
   }

   for (auto query : queries) {
      if (query.val > K) {
         result.push_back(total(BIT, query.index));
      }
      else {
         result.push_back(0);
      }
   }

   return result;
}

int main() {
   vector<int> arr = {3, 14, 32, 7, 11, 5, 8, 6, 16, 2, 15};
   vector<Query> queries = {{2, 4}, {5, 3}, {3, 6}, {0, 3}};
   int K = 2;

   vector<int> counts = elementsGreaterThanK(arr, queries, K);

   for (int count : counts) {
      cout << "Number of elements greater than " << K << ": " << count << endl;
   }

   return 0;
}

Output

Number of elements greater than 2: 2
Number of elements greater than 2: 5
Number of elements greater than 2: 3
Number of elements greater than 2: 0

in conclusion

We can simply iterate the array from index L to R and increment by 1 every time the array element is greater than K in order to find the answer to each query. However, in order to reduce the time complexity, we use Fenwick tree to perform such query operations. We can also use Line Segment Tree and Sparse Table instead of Fenwick tree to perform such query operations.

The above is the detailed content of Using a tree array (offline query), calculate the number of elements greater than K in the range L to R. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:tutorialspoint. If there is any infringement, please contact admin@php.cn delete
Gulc: C library built from scratchGulc: C library built from scratchMar 03, 2025 pm 05:46 PM

Gulc is a high-performance C library prioritizing minimal overhead, aggressive inlining, and compiler optimization. Ideal for performance-critical applications like high-frequency trading and embedded systems, its design emphasizes simplicity, modul

What are the types of values ​​returned by c language functions? What determines the return value?What are the types of values ​​returned by c language functions? What determines the return value?Mar 03, 2025 pm 05:52 PM

This article details C function return types, encompassing basic (int, float, char, etc.), derived (arrays, pointers, structs), and void types. The compiler determines the return type via the function declaration and the return statement, enforcing

What are the definitions and calling rules of c language functions and what are theWhat are the definitions and calling rules of c language functions and what are theMar 03, 2025 pm 05:53 PM

This article explains C function declaration vs. definition, argument passing (by value and by pointer), return values, and common pitfalls like memory leaks and type mismatches. It emphasizes the importance of declarations for modularity and provi

C language function format letter case conversion stepsC language function format letter case conversion stepsMar 03, 2025 pm 05:53 PM

This article details C functions for string case conversion. It explains using toupper() and tolower() from ctype.h, iterating through strings, and handling null terminators. Common pitfalls like forgetting ctype.h and modifying string literals are

Where is the return value of the c language function stored in memory?Where is the return value of the c language function stored in memory?Mar 03, 2025 pm 05:51 PM

This article examines C function return value storage. Small return values are typically stored in registers for speed; larger values may use pointers to memory (stack or heap), impacting lifetime and requiring manual memory management. Directly acc

distinct usage and phrase sharingdistinct usage and phrase sharingMar 03, 2025 pm 05:51 PM

This article analyzes the multifaceted uses of the adjective "distinct," exploring its grammatical functions, common phrases (e.g., "distinct from," "distinctly different"), and nuanced application in formal vs. informal

How does the C   Standard Template Library (STL) work?How does the C Standard Template Library (STL) work?Mar 12, 2025 pm 04:50 PM

This article explains the C Standard Template Library (STL), focusing on its core components: containers, iterators, algorithms, and functors. It details how these interact to enable generic programming, improving code efficiency and readability t

How do I use algorithms from the STL (sort, find, transform, etc.) efficiently?How do I use algorithms from the STL (sort, find, transform, etc.) efficiently?Mar 12, 2025 pm 04:52 PM

This article details efficient STL algorithm usage in C . It emphasizes data structure choice (vectors vs. lists), algorithm complexity analysis (e.g., std::sort vs. std::partial_sort), iterator usage, and parallel execution. Common pitfalls like

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools