There is hardly any need for improving the time complexity of initializing a Binary Indexed Tree (BIT). Anyway I want to share this neat little trick to initialize a BIT in O(N) time.

Let bit[N] be BIT array and a[N] be the array we need to initialize our BIT with. Notice that for all i we need to add a[i] to positions i, i + (i & -i) and so on in the bit array. Also, a[i + (i & -i)] will also be added to all these positions except i. We can add these 2 in the required places together! Take a look at the following code:

int bit[N], a[N];

void initialize(int n)
{
    for(int i=1; i<=n; i++)
    {
        bit[i] += a[i];
        if(i + (i & -i) <= n)
            bit[i + (i & -i)] += bit[i];
    }
}

Really easy and elegant! Although I have not come across any problems that needed this trick, but there might be a situation where N is too large to initialize the array in O(NlogN) while the number of queries are such that O(logN) per query is feasible (maybe in a 2D BIT problem).

The same technique can be for bulk updates (put update value for position i at a[i] for all N) and even for bulk queries. By bulk I mean number of updates/queries are O(N). Leaving bulk queries as an exercise for the reader :P (its really easy if you understood the above).

NOTE : Knowledge of Binary Indexed Trees is a prerequisite.

Problem Statement

Assume we need to solve the following problem. We have an array, A of length N with only non-negative values. We want to perform the following operations on this array:

1. Update value at a given position

2. Compute prefix sum of A upto i, i ≤ N

3. Search for a prefix sum (something like a lower_bound in the prefix sums array of A)

Problem Statement

We are going to deal with the well known knapsack problem with an additional constraint. We are given a list of N items and a knapsack of size W. Every item has a cost c_i associated with it (1 ≤ i ≤ N). We can select some items from the list such sum of the cost of all the selected items does not exceed W. The goal is tell for all w (0 ≤ w ≤ W), if we can select any number of items such that their total cost equals w. This is also known as the 0/1 knapsack problem. This can be easily solved in O(NW) time complexity using standard knapsack approach.

The addition constraint we have is .

The bounded knapsack problem

The bounded knapsack problem is like the 0/1 knapsack problem, except in this we are also given a count for each item. In other words, each item has a count s_i associated with it and we can select an item s_i times (1 ≤ i ≤ N).

Solving bounded knapsack problem

The solution is simple. Let dp[i][j] be the minimum count of ith item that has to be used to get a total cost of j while using some number (possibly 0) of first i items. If a total cost of j can not be obtained using first i items, then dp[i][j] =  - 1. The following code is used to calculate dp[i][j],

if(dp[i-1][j] >= 0)
    dp[i][j] = 0;
else if(dp[i][j - c[i]] >= 0 and dp[i][j - c[i]] < s[i])
    dp[i][j] = dp[i][j - c[i]] + 1;
else
    dp[i][j] = -1;

Here, c[i] is the cost and s[i] is the count for ith item. Also, dp[0][j] =  - 1 for all 1 ≤ j ≤ W and dp[0][0] = 0. Time complexity is O(NW).

Optimizing 0/1 Knapsack

Now we can present a faster solution to our problem. Notice that number of items is N and . Hence, there can only be unique costs. So we convert our problem to a bounded knapsack problem with unique items having some count. This can be solved in !!!

PS: I wrote this blog since I could not find a good source on the internet to learn about this approach. I hope there is no error since I really didn't read about this anywhere and worked out this approach myself.

EDIT: As some people have pointed out, this method has been discussed in some previous blogs (see comments for links). The only practise problem I could find is 755F. Also, the method discussed in this blog is not the most optimal one possible and can be optimized further using a bitset (which I will discuss in a future blog).

Suppose you want to solve a problem in which you have 3 types of queries in a grid of size N × N:
1. Insert a 1 in the grid at any position
2. Remove a 1 from any position in the grid
3. Count the number of 1 in a subgrid (ie. any rectangle inside the grid).
Initially the grid is empty and there are Q queries.

This can be solved easily by using a 2D BIT. But the conventional 2D BIT has space complexity O(N²). So if N <  = 10⁵, this won't work. Hence a compressed version of 2D BIT is required. This problem can be solved with an Implicit Treap along with BIT, but the implementation would be too complex. Here is an easy way to solve such a problem.

In this implementation an Order Statistics Tree (read about it here) is embedded at each node in a BIT. It only works if a 2D BIT has to be implemented for a grid of binary numbers (grid filled with only 1 or 0). The update() function has been broken into 2 functions — insert() (to insert a 1 in the grid at a given point) and remove() (to remove a 1 from the grid). The query() function counts number of 1s in the subgrid from (1, 1) to any given position in the grid.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mp make_pair
using namespace std;
using namespace __gnu_pbds;
typedef pair<int, int> pii;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> OST;

const int N = 100001;

OST bit[N];

void insert(int x, int y)
{
	for(int i = x; i < N; i += i & -i)
		bit[i].insert(mp(y, x));
}

void remove(int x, int y)
{
	for(int i = x; i < N; i += i & -i)
		bit[i].erase(mp(y, x));
}

int query(int x, int y)
{
	int ans = 0;
	for(int i = x; i > 0; i -= i & -i)
		ans += bit[i].order_of_key(mp(y+1, 0));
	return ans;
}

Time complexity : O(Qlog²(N))
Space complexity : O(Qlog(N))

Problems : Anton and Permutation, DISTNUM

PS: Suggestions are welcome. Please notify if there are any mistakes.