Several guides explain how Fenwick trees (BIT) work (and they do it pretty well), but I don't see any intuition or proof on it's correctness, specially the update operation. I've used BIT before and I know "how" it works, but not "why" the update operation works.

Here's the usual update code, taken from Topcoder's tutorial.

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

Popular guides on BIT (don't actually answer the "why" question):

Topcoder

GeeksForGeeks

Tushar Roy's video

Also, pllk recent book, page 86. Link

The following piece of code:

    const int N = 10;
    bool can[N];
    memset(can, -1, sizeof can);

    if(can[0] == 0) { // can[0] == false gives same result
        cout << "is zero";
    }
    else {
        cout << "not zero";
    }

Outputs is zero, however I expected it to be not zero.

Using memset like this instead:

    memset(can, 1, sizeof can); // using true instead of 1 gives same result

Outputs not zero as expected. What is going on?

For the following problem 543A - Writing Code, the jury's solution 11035704 optimize the DP solution explained in the contest's editorial http://codeforces.net/blog/entry/17773.

I understood the approach explained in the editorial, but what's the intuition behind the optimization and how it works? Specially the lines with bitwise operations:

    int i = it & 1;
        ...
        z[i][j][k] = z[i ^ 1][j][k];
  ...
    ans += z[n & 1][bl][i];
  ...

Just to be clear: I'm not asking about the bitwise operations alone, but also how the original solution in the editorial translated to the jury's code. For example, if you maintain only the two last rows of the DP, how are you going to construct the problem's solution (output)? Thanks.

Problem link: http://codeforces.net/contest/479/problem/C

AC submission (sorting a vector): http://codeforces.net/contest/479/submission/16772060

WA submission (using map): http://codeforces.net/contest/479/submission/16772083

I used a greedy approach in the WA submission. It's possible to take any exam scheduled to the day A before day A. Suppose that the in the final solution for the problem all the exams scheduled to the day A are taken before A. If this is true, the last exam will be completed in the greatest number B, such that B is smaller than A, within all elements in the set of exams scheduled to the day A. This greedy step translates to code like this:

auto at = mp.find(a);
if(at != mp.end()) {
    at->second = max(at->second, b);
}
else {
    mp[a] = b;
}

If this step is not possible, consider the first element C > A such that mp[C] < mp[A], so I cant take exam C in the day mp[C]. So the next minimum value available is C. This step is done in nom-increasing order of A. But I got WA with this solution and have no ideia why.