首页 > 其他分享 >2维区间树状数组

2维区间树状数组

时间:2023-11-21 20:13:18浏览次数:28  
标签:树状 int ll 数组 区间 void

void add(ll x, ll y, ll z)
{
    for(int X = x; X <= n; X += X & -X)
        for(int Y = y; Y <= m; Y += Y & -Y)
        {
            t1[X][Y] += z;
            t2[X][Y] += z * x;
            t3[X][Y] += z * y;
            t4[X][Y] += z * x * y;
        }
}
void range_add(ll xa, ll ya, ll xb, ll yb, ll z)
{   //(xa, ya) 到 (xb, yb) 的矩形
    add(xa, ya, z);
    add(xa, yb + 1, -z);
    add(xb + 1, ya, -z);
    add(xb + 1, yb + 1, z);
}

//区间修改
ll ask(ll x, ll y)
{
    ll res = 0;
    for(int i = x; i; i -= i & -i)
        for(int j = y; j; j -= j & -j)
            res += (x + 1) * (y + 1) * t1[i][j]- (y + 1) * t2[i][j]- (x + 1) * t3[i][j]+ t4[i][j];
            return res;
}    
ll range_ask(ll xa, ll ya, ll xb, ll yb)
{
    return ask(xb, yb) - ask(xb, ya - 1) - ask(xa - 1, yb) + ask(xa - 1, ya - 1);
}//区间查询

标签:树状,int,ll,数组,区间,void
From: https://www.cnblogs.com/kids1412/p/17847452.html

相关文章

  • LeetCode-Java:88合并两个有序数组
    题目:给你两个按非递减顺序排列的整数数组nums1和nums2,另有两个整数m和n,分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中,使合并后的数组同样按非递减顺序排列。注意:最终,合并后数组不应由函数返回,而是存储在数组nums1中。为了应对这种情况,nums1......
  • 三种办法遍历对象数组,获取数组对象中所有的属性值(key,value);四种方法查找对象数组里面
    一,获取对象数组中某属性的所有值如果是要获取具体第几个属性的值,倒是可以用arr[i].name的方法来实现。若是全部的属性的值,并返回一个新的数组嘞,思路是加循环遍历方法如下。1、from方法vararr=[{id:1,name:"小明"},{id:2......
  • [4] 寻找两个正序数组的中位数
    /***@param{number[]}nums1*@param{number[]}nums2*@return{number}*/varfindMedianSortedArrays=function(nums1,nums2){constnums=nums1.concat(nums2).sort((a,b)=>a-b)constll=nums.lengthif(ll%2===0){return......
  • 区间dp
    1.acwing282石子合并问题1#include<bits/stdc++.h>2usingnamespacestd;34intn;5constintN=310;6ints[N];7intf[N][N];89intmain()10{11scanf("%d",&n);12for(inti=1;i<=n;i++)scanf(&qu......
  • 数组中的指定某一项放置第一位
    constarr=[]this.todoLeftList.forEach((item)=>{arr.push(item.srcSystemCode)})constindex=arr.indexOf('zldc')if(index){constfirst=this.todoLeftList.splice(index,1)[0]this.todoLeftList.unshift(first)} constarr=[]this.tod......
  • 【数据结构】数组和字符串(四):特殊矩阵的压缩存储:稀疏矩阵——三元组表
    4.2.1矩阵的数组表示【数据结构】数组和字符串(一):矩阵的数组表示4.2.2特殊矩阵的压缩存储  矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等,如果用这种方式存储,会出现大量存储空间存放重复信息或零......
  • 算法刷题记录-两个数组的交集
    算法刷题记录-两个数组的交集两个数组的交集给定两个数组nums1和nums2,返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。示例1:输入:nums1=[1,2,2,1],nums2=[2,2]输出:[2]示例2:输入:nums1=[4,9,5],nums2=[9,4,9,8,4]......
  • 数组
    本章重点1.一维数组的创建和初始化2.一维数组的使用3.一维数组在内存中的储存4.二维数组的创建和初始化5.二维数组的使用6.二维数组在内存中的储存7.数组作为函数参数8.数组的应用实例1:三子棋9.数组的应用实例2:扫雷游戏正文开始1.一维数组的创建和初始化(1)数组的创建数组是一组相同......
  • 判断数组
    判断数组1.通过Array.isArray()判断Array.isArray()用于确定传递的值是否是一个数组,返回一个布尔值leta=[7,8,9];Array.isArray(a);//true2.通过instanceof判断instanceof运算符用于检验构造函数的prototype属性是否出现在对象的原型链中的任何位置,返回一个布尔值let......
  • 定义动态数组,完成6个评委打分
    importjava.util.Scanner;publicclassPingWei{publicstaticvoidmain(String[]args){//题目:定义动态数组,完成6个评委打分doublepingwei[]=newdouble[6];//定义6个数组Scannerscann......