CODEWITHSUNDEEP
c++arraysalgorithmdata-structuresstl
Garrick
Garrick

Reputation: 689

Number of occurences of a number in all the queries?

Take an unsorted array like:

4,5,1,2,3,7,8,3

and queries be like:

[1 2] [5 5] [2 6] [6 6] [1 6] [1 5]

where each query represents a interval of indices.

Length of array and total queries can be upto 100000.

I want to calculate the number of occurences of every index in each of the queries like below:

occurences of 1: 3

occurences of 3: 3

occurences of 5: 4, etc

Any optimal way to perform this ? I have tried in naive way but need some hints for optimal solution.

Upvotes: 0

Views: 72

Answers (1)

GolamMazid Sajib
GolamMazid Sajib

Reputation: 9447

You can solve it by BIT(binary index tree) or Segment-Tree..

I attached two link there to learn about those algoritm...

BIT solution:

For each query lets range: [l r] :

  • Now you need to update in BIT l to n with value 1.
  • Now you need to exclude update r+1 to n...so update r+1 to n with value -1 in BIT..

Each update operation take log(n) in BIT...

Calculate number of occurances for each index:

Call sum(index) in BIT to get count

This operation take log(n) time..

Complexity:

complexity of this solution: Q*(log(n)+log(n)) + N *(log(n))..

Code:

#include <bits/stdc++.h>
using namespace std;
int tree[100005], A[100005];

void update(int idx, int n, int v) {
    while (idx <= n) {
        tree[idx] += v;
        idx += (idx & -idx);
    }
}

int sum(int idx) {
    int res = 0;
    while (idx) {
        res += tree[idx];
        idx -= (idx & -idx);
    }
    return res;
}

int main() {
    int n, q, i, l, r;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d", &q);
    memset(tree, 0, sizeof(tree));
    while (q--) {
        scanf("%d%d", &l, &r);
        update(l,n,1);
        update(r+1,n,-1);
    }
    for (i = 1; i <= n; i++) {
        printf("%d\n", sum(i));
    }
    return 0;
}

Upvotes: 1

Related Questions