rsq.rar_RSQ RMQ_range-sketch query

/* * Copyright(c) 2009-2010 * written by Zhumazhanov Adlet */ #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <cassert> #include <cstring> #include <conio.h> #define PROBLEM_NAME "a" #define MAX_N (int)1e3+1 #define PREV(x) ((x)&(x-1)) #define NEXT(x) (((x) << 1) - PREV(x)) using namespace std; int n, m, a[MAX_N], f[MAX_N]; void init_rsq(const int& n) { for (int i = 0; i <= n; ++ i) f[i] = 0; } int rsq(int i) { int result = 0; while (i > 0) { result += f[i]; i = PREV(i); } return result; } int rsq(int l, int r) { return rsq(r)-rsq(l-1); } void modify(int i, int d) { while (i <= n) { f[i] += d; i = NEXT(i); } } int main() { assert (freopen(PROBLEM_NAME".in", "r", stdin)); assert (freopen(PROBLEM_NAME".out", "w", stdout)); scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]); init_rsq(n); for (int i = 1; i <= n; ++ i) modify(i, a[i]); int l, r; for (int i = 0; i < m; ++ i) { scanf("%d%d", &l, &r); printf("%d\n", rsq(l, r)); } return 0; }