Cod sursa(job #1957551)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 7 aprilie 2017 16:50:08
Problema Arbori indexati binar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

class FenwickTree {
  public:
    FenwickTree(int const _size) :
      size(_size),
      tree(vector<int>(_size + 1, 0)) {}

    void update(int where, int const value) {
        for (++where; where <= size; where += lsb(where)) {
            tree[where] += value;
        }
    }

    int query(int where) const {
        int sum = 0;
        for (++where; where > 0; where -= lsb(where)) {
            sum += tree[where];
        }
        return sum;
    }

    int query(int const from, int const to) const {
        return query(to) - query(from - 1);
    }

    int lowerBound(int const value) const {
        int step = 1, sum = 0, where = 0;
        for (; step <= size; step <<= 1);
        for (; step > 0; step >>= 1) {
            if (where + step <= size && sum + tree[where + step] < value) {
                sum += tree[where += step];
            }
        }
        return where;
    }

  private:
    int size;
    vector<int> tree;

    static int lsb(int const value) {
        return value & (-value);
    }
};

int main() {
    ifstream in("aib.in");
    ofstream out("aib.out");
    int n, q;
    in >> n >> q;
    auto tree = FenwickTree(n);
    for (int i = 0; i < n; i++) {
        int value;
        in >> value;
        tree.update(i, value);
    }
    for (; q > 0; --q) {
        int type;
        in >> type;
        if (type == 0) {
            int where, value;
            in >> where >> value;
            tree.update(where - 1, value);
        } else if (type == 1) {
            int from, to;
            in >> from >> to;
            out << tree.query(from - 1, to - 1) << "\n";
        } else {
            int value;
            in >> value;
            int const where = tree.lowerBound(value);
            out << (tree.query(where) == value ? where + 1 : -1) << "\n";
        }
    }
    in.close();
    out.close();
    return 0;
}