I found that many people use x += x & (-x), x -= x & (-x) to solve the interval tree problem (While implementing data structures like segment tree, binary indexed tree etc).
Can you explain what that equation means?
For Example:
void update(int m, int x) {
m++;
while (m < N) {
t[m] = t[m] + x;
m += m & -m;
}
}
int query(int m) {
int result= 0;
m++;
while (m > 0) {
result = result + t[m];
m -= m & -m;
}
return result;
}
Note: This answer (like the method itself) assumes signed integers are represented in two's complement form.
The expression x & -x is a quick - but admittedly arcane - way of getting the value represented by the lowest set bit in x (when all other bits are clear). This is sometimes known as the weight of the bit, and is numerically equal to 2 raised to the power of the bit's position (where the least significant bit is position 0).
The method relies on the fact that there can only be a single bit that is set in the binary (2s-comp) representations of both x and -x - and this will actually be the least significant set bit in x.
There are some good explanations of how this works, with many examples, here on Quora.
In the update and query functions you show, the amount by which to increase/decrease m in the while loops is thus weighted according to the position of the least significant set bit in the (original) m.
Feel free to ask for further clarification and/or explanation (but I don't wish to copy/paste or paraphrase too much of the discussion I've linked).