给定一个数组，支持两种操作：
1.查询区间和
2.修改某个元素的值
示例：
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
class NumArray {
int n;
vector<int> A;
vector<int> C;
// 求 2^k，其中 k 表示 x 二进制位中后缀 0 的个数
int lowbit(int x) {
return x & (-x);
}
// 更新 C 数组，对 A[x] 的每个祖先都加上 delta：
// 如果是初始化阶段 delta = A[i]，如果是更新 A[i]，则 delta = new_val - A[i]
void updateC(int x, int delta) {
for (int i = x; i <= n; i += lowbit(i)) {
C[i] += delta;
}
}
// 求前缀区间 [1, x] 的和
int sumPrefix(int x) {
int res = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
res += C[i];
}
return res;
}
public:
// 初始化
NumArray(vector<int> nums) {
n = nums.size();
A.resize(n + 1, 0);
C.resize(n + 1, 0);
for (int i = 1; i <= n; i++) {
A[i] = nums[i - 1]; // 树状数组的内部默认从 1 开始计数
updateC(i, A[i]);
}
}
// 将 A[i] 的值更新为 val
void update(int i, int val) {
i++; // 树状数组的内部默认从 1 开始计数，如果外部默认从 0 开始计数，则需要 +1;
updateC(i, val - A[i]); // 更新 A[i] 的所有祖先节点，加上 val 与 A[i] 的差即可
A[i] = val;
}
// 求范围 [lo, hi] 的区间和
int sumRange(int lo, int hi) {
lo++; hi++; // 树状数组的内部默认从 1 开始计数，如果外部默认从 0 开始计数，则需要 +1;
return sumPrefix(hi) - sumPrefix(lo - 1);
}
};
void solve() {
vector<int> nums{1, 3, 5};
auto na = NumArray(nums);
int ret;
ret = na.sumRange(0, 2);
na.update(1, 2);
ret = na.sumRange(0, 2);
}
// 缓存节点（双端队列）
struct CacheNode {
int key;
int value;
CacheNode *pre, *next;
CacheNode(int k, int v) : key(k), value(v), pre(nullptr), next(nullptr) {}
};
class LRUCache {
int size = 0;
CacheNode* head = nullptr;
CacheNode* tail = nullptr;
unordered_map<int, CacheNode*> dp; // hash_map
void remove(CacheNode *node) {
if (node != head) { // 修改后序节点是需判断是否头结点
node->pre->next = node->next;
}
else {
head = node->next;
}
if (node != tail) { // 修改前序节点是需判断是否尾结点
node->next->pre = node->pre;
}
else {
tail = node->pre;
}
// remove 时不销毁该节点
//delete node;
//node = nullptr;
}
void setHead(CacheNode *node) {
node->next = head;
node->pre = nullptr;
if (head != nullptr) {
head->pre = node;
}
head = node;
if (tail == nullptr) {
tail = head;
}
}
public:
LRUCache(int capacity) : size(capacity) { }
int get(int key) {
auto it = dp.find(key);
if (it != dp.end()) {
auto node = dp[key];
// 如果命中了，把该节点移动到头部
remove(node);
setHead(node);
return node->value;
}
return -1;
}
void put(int key, int value) {
auto it = dp.find(key);
if (it != dp.end()) {
auto node = dp[key];
node->value = value; // 更新
remove(node);
setHead(node);
}
else {
auto node = new CacheNode(key, value);
setHead(node);
dp[key] = node;
// 关键：判断容量
//if (dp.size() >= size) { // 若先删除节点，则为 >=
if (dp.size() > size) { // 若先存入 dp，则为 >
auto it = dp.find(tail->key);
remove(tail);
// 这里才销毁内存（即使不销毁也能过 LeetCode）
delete it->second;
it->second = nullptr;
dp.erase(it); // 先销毁，在移除
}
}
}
};
