Cod sursa(job #2565041)

Utilizator NotTheBatmanBruce Wayne NotTheBatman Data 2 martie 2020 11:47:01
Problema Arbori indexati binar Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;

const int N = 1e5 + 5;

class Fenwick_Tree
{
public:
    void Get_Length(int x)
    {
        len = x;
    }
    void Update (int pos, int val)
    {
        for (; pos <= len; pos += (pos & -pos))
            aib[pos] += val;
    }
    int Sum (int pos)
    {
        int s;
        for (s = 0; pos > 0; pos -= (pos & - pos))
            s += aib[pos];
        return s;
    }
    int SegmentQuery (int x, int y)
    {
        return Sum(y) - Sum(x - 1);
    }
    int PositionQuery (int s)
    {
        int left, right, mid, pos;
        left = 1;
        right = len;
        while (left <= right)
        {
            mid = (left + right) / 2;
            int x = Sum(mid);
            if (x == s)
            {
                pos = mid;
                right = mid - 1;
            }
            else if (x < s)
                left = mid + 1;
            else right = mid - 1;
        }
        return pos;
    }
private:
    int aib[N], len;
};

void Read ()
{
    int q, n;
    ifstream fin ("aib.in");
    ofstream fout ("aib.out");
    fin >> n >> q;
    Fenwick_Tree bit;
    bit.Get_Length(n);
    for (int i = 1, x; i <= n; i++)
    {
        fin >> x;
        bit.Update(i, x);
    }
    while (q--)
    {
        int op, x, y;
        fin >> op;
        if (op == 0)
        {
            fin >> x >> y;
            bit.Update(x, y);
        }
        else if (op == 1)
        {
            fin >> x >> y;
            fout << bit.SegmentQuery(x, y) << "\n";
        }
        else
        {
            fin >> x;
            fout << bit.PositionQuery(x) << "\n";
        }
    }
    fout.close();
}

int main()
{
    Read();
    return 0;
}