bit Algorithm

The bit algorithm, also known as bitwise algorithm, is a collection of computer programming techniques that apply operations on individual bits of data. These operations are often used in low-level programming and computer hardware design, as they are efficient and can be executed quickly. Bitwise algorithms involve manipulating binary data by performing logical operations like AND, OR, XOR, and NOT, as well as shifting bits within a binary number. These techniques are essential for tasks such as data compression, encryption, and error detection, allowing computers to process and store information more effectively. Bitwise algorithms are particularly useful in situations where performing operations on an entire byte or word of data is unnecessary or inefficient. For example, a programmer may need to toggle a specific bit within a binary number without changing the other bits. By utilizing bitwise operations, the programmer can quickly and efficiently manipulate the desired bit without having to process the entire number. Additionally, bitwise algorithms can be used in computer graphics and image processing, where individual pixels may be represented by bits and manipulated using bitwise operations. As a result, the bit algorithm plays a crucial role in the overall performance and functionality of modern computing systems.
// Binary Indexed Tree.
#include <iostream>

using namespace std;

class Bit
{
    int n;
    vector<int> bit;
    inline int offset(int x)
    {
        return (x & (-x));
    }

    public:

        Bit(vector<int>& arr)
	{
            n = arr.size();
            bit.assign(n + 1, 0);
            for (int i = 0; i < n; ++i)
	    {
                update(i, arr[i]);
            }
        }
    Bit(int x)
    {
        n = x;
        bit.assign(n + 1, 0);
    }

    void update(int id, int val)
    {
        // Add val at id
        id++;
        while (id <= n)
	{
            bit[id] += val;
            id += offset(id);
        }
    }

    int sum(int id)
    {
        // Get prefix sum upto id.
        id++;
        int res = 0;
        while (id > 0)
	{
            res += bit[id];
            id -= offset(id);
        }
        return res;
    }

    int sum_range(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
};

int main()
{
    int n = 5;
    vector<int> arr = { 1, 2, 3, 4, 5 };
    Bit x(arr);

    assert(x.sum_range(0, 0) == 1);
    assert(x.sum_range(0, 1) == 3);
    assert(x.sum_range(0, 2) == 6);
    x.update(0, 6);
    assert(x.sum_range(0, 0) == 6);
    assert(x.sum_range(0, 1) == 8);
    assert(x.sum_range(0, 2) == 11);
	return 0;
}

LANGUAGE:

DARK MODE: